再帰はコンピューター科学と数学の基本的な概念であり、関数がそれ自体を呼び出すことを可能にし、反復ステップを通じて複雑な問題を解決できるようにします。再帰関数の実行を理解および分析するために一般的に使用される視覚的表現の 1 つは、再帰ツリーです。この記事では、再帰ツリーの背後にある理論、その構造、再帰アルゴリズムを理解する上での重要性について説明します。
再帰ツリーとは何ですか?
再帰ツリーは、再帰関数の実行フローを示すグラフィック表現です。再帰呼び出しを視覚的に詳細に示し、アルゴリズムが分岐して最終的に基本ケースに到達するまでの進行を示します。ツリー構造は、時間の複雑さを分析し、関係する再帰的なプロセスを理解するのに役立ちます。
ツリー構造
再帰ツリー内の各ノードは、特定の再帰呼び出しを表します。最初の呼び出しは上部に示されており、後続の呼び出しはその下に分岐します。ツリーは下に向かって成長し、階層構造を形成します。各ノードの分岐係数は、関数内で行われる再帰呼び出しの数によって異なります。さらに、ツリーの深さは、基本ケースに到達するまでの再帰呼び出しの数に対応します。
規範事例
基本ケースは、再帰関数の終了条件として機能します。これは、再帰が停止し、関数が値を返し始めるポイントを定義します。再帰ツリーでは、基本ケースを表すノードは、さらなる再帰呼び出しをもたらさないため、通常、リーフ ノードとして表されます。
再帰呼び出し
再帰ツリーの子ノードは、関数内で行われる再帰呼び出しを表します。各子ノードは個別の再帰呼び出しに対応し、その結果、新しいサブ問題が作成されます。これらの再帰呼び出しに渡される値またはパラメーターは異なる場合があり、その結果、サブ問題の特性が変化することがあります。
実行フロー:
再帰ツリーをたどると、再帰関数の実行フローについての洞察が得られます。ルート ノードでの最初の呼び出しから開始して、基本ケースに遭遇するまで分岐をたどって後続の呼び出しに到達します。基本ケースに達すると、再帰呼び出しが戻り始め、ツリー内のそれぞれのノードが戻り値でマークされます。走査は、ツリー全体が走査されるまで続けられます。
時間計算量の分析
再帰ツリーは、再帰アルゴリズムの時間計算量の分析に役立ちます。ツリーの構造を調べることで、行われた再帰呼び出しの数と各レベルで行われた作業を判断できます。この分析は、アルゴリズムの全体的な効率を理解し、潜在的な非効率性や最適化の機会を特定するのに役立ちます。
導入
- 数値の階乗を求めるプログラムを考えてみましょう。この関数は数値 N を入力として受け取り、結果として N の階乗を返します。この関数の疑似コードは次のようになります。
// find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ - 再帰の例としては、前述の関数があります。数値の階乗を決定する関数を呼び出しています。次に、同じ数値のより小さい値が与えられると、この関数はそれ自体を呼び出します。これは、関数呼び出しがなくなる基本的なケースに到達するまで続きます。
- 再帰は、結果が同じ問題の小さなインスタンスの結果に依存する場合に、複雑な問題を処理するための手法です。
- 関数について考えると、基本ケースに到達するまで関数自体を呼び出し続ける場合、その関数は再帰的であると言われます。
- 再帰関数には、基本ケースと再帰ステップという 2 つの主要なコンポーネントがあります。基本ケースに到達したら、再帰フェーズへの移行を停止します。無限の再帰を防ぐには、基本ケースを適切に定義する必要があり、これは非常に重要です。無限再帰の定義は、基本ケースに到達しない再帰です。プログラムが基本ケースに到達しない場合、スタック オーバーフローが発生し続けます。
再帰の種類
一般に、再帰には 2 つの異なる形式があります。
- 線形再帰
- ツリー再帰
- 線形再帰
線形再帰
- 実行するたびに自分自身を 1 回だけ呼び出す関数は、線形再帰的であると言われます。線形再帰のわかりやすい例は、階乗関数です。 「線形再帰」という名前は、線形再帰関数の実行に線形の時間がかかるという事実を指します。
- 以下の疑似コードを見てください。
function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } - 関数 doSomething(n) を見ると、この関数は n という名前のパラメータを受け入れ、いくつかの計算を行ってから、より低い値で同じプロシージャをもう一度呼び出します。
- doSomething() メソッドが引数値 n を指定して呼び出されたとき、T(n) が計算を完了するのに必要な合計時間を表すとします。このため、漸化式 T(n) = T(n-1) + K を定式化することもできます。ここで K は定数として機能します。関数が変数にメモリを割り当てたり割り当て解除したり、数学的演算を実行したりするには時間がかかるため、定数 K が含まれています。時間は非常に微小で重要ではないため、時間を定義するために K を使用します。
- この再帰的プログラムの時間計算量は、最悪のシナリオではメソッド doSomething() が n 回呼び出されるため、単純に計算できます。正式に言えば、関数の時間的複雑さは O(N) です。
ツリー再帰
- 再帰の場合に複数回再帰呼び出しを行う場合、それはツリー再帰と呼ばれます。ツリー再帰の効果的な例は、フィボナッチ数列です。ツリー再帰関数は指数時間で動作します。時間的な複雑さは線形ではありません。
- 以下の疑似コードを見てください。
function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } - このコードと前のコードの唯一の違いは、このコードでは、n の値を小さくして同じ関数をもう 1 回呼び出していることです。
- この関数の漸化式として T(n) = T(n-1) + T(n-2) + k を置きましょう。 K は再び定数として機能します。
- より小さい値で同じ関数への呼び出しが複数回実行される場合、この種の再帰はツリー再帰として知られています。ここで興味深いのは、この機能にどれくらい時間がかかるかということです。
- 同じ関数について、以下の再帰ツリーに基づいて推測してください。
- 特にツリー再帰の場合、再帰関数を直接見て時間計算量を推定するのは難しいと思われるかもしれません。再帰ツリー法は、このような関数の時間的複雑さを計算するためのいくつかの手法のうちの 1 つです。さらに詳しく調べてみましょう。
再帰ツリー法とは何ですか?
- T(N) = T(N/2) + N のような再帰関係、または再帰の種類のセクションで前に説明した 2 つの再帰関係は、再帰ツリー アプローチを使用して解決されます。これらの反復関係では、多くの場合、問題に対処するために分割統治戦略が使用されます。
- 大きな問題をより小さなサブ問題に分割するときに作成される、より小さなサブ問題への回答を統合するには時間がかかります。
- たとえば、マージ ソートの場合、再帰関係は T(N) = 2 * T(N/2) + O(N) となります。合計サイズ T(N/2) の 2 つのサブ問題の答えを組み合わせるのに必要な時間は O(N) であり、これは実装レベルでも当てはまります。
- たとえば、二分探索の漸化式は T(N) = T(N/2) + 1 であるため、二分探索を反復するたびに検索空間が半分になることがわかります。結果が決定したら、関数を終了します。これは定数時間の操作であるため、漸化関係には +1 が追加されます。
- 漸化式 T(n) = 2T(n/2) + Kn を考慮する必要があります。 Kn は、n/2 次元のサブ問題に対する答えを組み合わせるのに必要な時間を示します。
- 前述の漸化関係の再帰木を描いてみましょう。
上記の再帰ツリーを研究することで、次のようないくつかの結論を導き出すことができます。
1. ノードの価値を決定するために重要なのは、各レベルの問題の大きさだけです。問題のサイズは、レベル 0 では n、レベル 1 では n/2、レベル 2 では n/2 などとなります。
2. 一般に、ツリーの高さは log (n) に等しいと定義します。ここで、n は問題のサイズであり、この再帰ツリーの高さはツリー内のレベル数に等しくなります。これは真実です。なぜなら、先ほど確立したように、分割統治戦略は問題を解決するために漸化式によって使用され、問題サイズ n から問題サイズ 1 に到達するには単純に log (n) ステップを実行する必要があるからです。
- たとえば、N = 16 の値を考えてみましょう。各ステップで N を 2 で割ることができる場合、N = 1 を得るには何ステップが必要ですか?各ステップで 2 で割っていることを考慮すると、正解は 4、つまり log(16) 底 2 の値です。
log(16) 底 2
log(2^4) 底 2
4 * log(2) 底 2、log(a) 底 a = 1 なので
したがって、4 * log(2) 底 2 = 4
3. 各レベルで、漸化式の第 2 項が根とみなされます。
この戦略の名前には「ツリー」という単語が含まれていますが、これを理解するのに木の専門家である必要はありません。
再帰ツリーを使用して再帰関係を解くにはどうすればよいですか?
再帰ツリー手法におけるサブ問題のコストは、サブ問題を解くのに必要な時間です。したがって、再帰ツリーにリンクされている「コスト」というフレーズに気付いた場合、それは単に特定の下位問題を解決するのに必要な時間を指します。
いくつかの例を挙げて、これらすべての手順を理解しましょう。
例
漸化式を考えてみると、
T(n) = 2T(n/2) + K
解決
与えられた漸化関係は次の性質を示します。
問題サイズ n は、それぞれサイズ n/2 の 2 つのサブ問題に分割されます。これらの下位問題に対する解を組み合わせるコストは K です。
サイズ n/2 の各問題は、それぞれサイズ n/4 の 2 つのサブ問題に分割されます。
最後のレベルでは、部分問題のサイズが 1 に減ります。つまり、最終的に基本ケースに到達します。
夕食対夕食
この漸化関係を解く手順に従ってみましょう。
ステップ 1: 再帰ツリーを描画する
ステップ 2: 木の高さを計算する
数値を 2 で割り続けると、この数値が 1 になるときが来ることがわかっているため、問題のサイズ N と同様に、K 回 2 で除算した後、N が 1 に等しくなるとしましょう。これは、次のことを意味します。 n / 2^k) = 1
ここで、n / 2^k は最後のレベルの問題のサイズであり、常に 1 に等しくなります。
これで、log() を両辺に取り込むことで、上記の式から k の値を簡単に計算できます。以下はより明確な導出です。
n = 2^k
- log(n) = log(2^k)
- log(n) = k * log(2)
- k = log(n) / log(2)
- k = log(n) 底 2
したがって、木の高さは log (n) 底 2 になります。
ステップ 3: 各レベルのコストを計算する
- レベル 0 のコスト = K、2 つのサブ問題がマージされます。
- レベル 1 のコスト = K + K = 2*K、2 つの副問題は 2 回マージされます。
- レベル 2 のコスト = K + K + K + K = 4*K、2 つの副問題が 4 回マージされます。等々....
ステップ 4: 各レベルのノード数を計算する
まず、最後のレベルのノードの数を決定しましょう。再帰ツリーから、これを推測できます
- レベル 0 には 1 (2^0) ノードがあります
- レベル 1 には 2 (2^1) ノードがあります
- レベル 2 には 4 (2^2) ノードがあります
- レベル 3 には 8 (2^3) ノードがあります
したがって、レベル log(n) には 2^(log(n)) ノード、つまり n 個のノードが必要です。
ステップ 5: すべてのレベルのコストを合計する
- 総コストは次のように書くことができます。
- 合計コスト = 最後のレベルを除くすべてのレベルのコスト + 最後のレベルのコスト
- 合計コスト = レベル 0 のコスト + レベル 1 のコスト + レベル 2 のコスト +.... + レベルログ (n) のコスト + 最後のレベルのコスト
最後のレベルのコストは、これが基本ケースであり、最後のレベルではマージが行われないため、個別に計算されます。そのため、このレベルで 1 つの問題を解決するコストは一定の値になります。それをO(1)としましょう。
数値を式に代入してみましょう。
- T(n) = K + 2*K + 4*K + .... + log(n)` 回 + `O(1) * n
- T(n) = K(1 + 2 + 4 + .... + log(n) 回)` + `O(n)
- T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) 回 + O(n)
上の式をよく見てみると、幾何級数（a、ar、ar^2、ar^3……無限時間）を形成しています。 GP の合計は、S(N) = a / (r - 1) で求められます。ここに第 1 項があり、r は公比です。