recursion - 再帰関係から再帰木の高さを決定する方法は?

Question

再帰ランタイムを処理するときに構築された再帰ツリーの高さを決定するにはどうすればよいでしょうか? 通常の木の高さを決定するのとどう違うのですか?

代替テキスト http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

編集：申し訳ありませんが、再帰関係から再帰ツリーの高さを取得する方法を追加するつもりでした。

Answer 1

再帰が T(n) = aT(n/b) + f(n) の形式である場合、ツリーの深さは n の対数ベース b です。

たとえば、2T(n/2) + n の再帰には、深さ lg(n) (n の底が 2 の対数) のツリーがあります。

Answer 2

再帰ツリーの高さは、問題の再帰アルゴリズムによって異なります。すべてのツリー構造が均一な高さを持っているわけではないのと同様に、すべての分割統治アルゴリズムが均一な高さのツリーを持っているわけではありません。アルゴリズムの可能な最大の高さを決定できない場合、または実行時にツリーの実際の高さを計算する必要がある場合は、再帰関数に対してグローバル変数を使用し、関数へのエントリ時にそれをインクリメントし、デクリメントします。関数の終了時にそれ。この変数は、再帰プロシージャの現在のレベルを示します。必要に応じて、この変数の最大値を 2 番目の変数で維持できます。