再帰
最終更新
再帰とは、同じ問題のより小さな版に対して関数が自分自身を呼び出し、直接答えられるほど小さなケースに到達するまでそれを繰り返すことです。その直接答えられるケースがベースケースであり、すべての再帰関数には必ず1つ必要です。fib(n) は fib(n - 1) と fib(n - 2) に分かれ続け、fib(1) または fib(0) に達すると、それらは自分自身の値をそのまま返します。上の可視化はまさにこれを実行しています。再生を押すと、呼び出しが木のように枝分かれし、葉でベースケースに到達し、そこから値を上へ返しながら各段で組み合わせていく様子が見られます。
アニメーションが示すもう1つのものが呼び出しスタック、つまり開始したもののまだ返っていないすべての呼び出しです。スタックは呼び出しが深くなるにつれて伸び、再帰の深さで最大になり、結果が返るにつれてほどけていきます。だからこそ深い再帰はスタックオーバーフローを起こしうる一方、反復ループはスタックを一切伸ばしません。同じ呼び出しの形が 深さ優先探索、マージソート、そして 二分木 に対するほとんどの操作を動かしています。
時間計算量と空間計算量
上で示した素朴な再帰版フィボナッチと、標準的な2つの改善策について：
| 手法 | 時間 | 空間 | 備考 |
|---|---|---|---|
| 素朴な再帰 | O(2^n) | O(n) | 呼び出し木は各段で2倍になる。空間は木全体ではなく、最も深いスタックの分だけ。 |
| メモ化あり | O(n) | O(n) | 各 fib(k) は一度だけ計算してキャッシュする。重複する部分木は参照に置き換わる。 |
| 反復ループ | O(n) | O(1) | 2つの変数を転がすだけで、スタックは完全に不要になる。 |
| 一般の再帰全般 | 呼び出し回数 × 1回あたりの仕事量 | O(max depth) | スタックは、開始したがまだ返っていない呼び出しごとに1つのフレームを保持する。 |
ステップごとの手順
| ステップ | 何が起きるか |
|---|---|
| 1 | 最初の呼び出し fib(n) が呼び出しスタックに積まれる。 |
| 2 | その呼び出しには fib(n - 1) が必要なので、それもスタックに積まれる。親は待機する。 |
| 3 | n <= 1 かどうかを問う呼び出しが現れるまで、呼び出しは入れ子になり続ける。ベースケースは即座に答え、それより深くは呼び出さない。 |
| 4 | ベースケースの値が親に返り、親は2つ目の呼び出し fib(n - 2) を開始できるようになる。 |
| 5 | 両方の子が返ると、親はそれらを足して自分も返る。そのフレームはスタックから外れる。 |
| 6 | この返却が木を上へたどって繰り返され、最初の呼び出しのフレームが最終的な答えとともに取り除かれて、スタックが空になる。 |
具体例
アニメーションの再生順そのままに、fib(4) を正確な呼び出し順で評価すると：
| 呼び出し | その時点のスタック | 返り値 |
|---|---|---|
fib(4) | fib(4) | 子を待つ |
fib(3) | fib(4) > fib(3) | 子を待つ |
fib(2) | fib(4) > fib(3) > fib(2) | 子を待つ |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1（ベースケース） |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0（ベースケース） |
fib(2) を合成 | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1（ベースケース） |
fib(3) を合成 | fib(4) > fib(3) | 1 + 1 = 2 |
再び fib(2) | fib(4) > fib(2) | 1、ゼロから再計算 |
fib(4) を合成 | fib(4) | 2 + 1 = 3 |
再帰を使うべきとき
| 使うべきとき | 避けるべきとき |
|---|---|
| 問題が自己相似のとき：木、入れ子構造、分割統治 | 同じことがスタックフレームなしの単純なループで書けるとき |
深さが有界で控えめなとき。たとえば マージソート の O(log n) | 巨大な入力で深さが入力サイズに達しうるとき。スタックオーバーフローの危険がある |
| バックトラッキングで、どこから再開するかをスタックに覚えさせる必要があるとき | 同じ部分問題が繰り返し現れるのに、それをキャッシュしていないとき |
| 再帰版のほうが明らかに読みやすく、検証もしやすいとき | 呼び出しのオーバーヘッドが実測で効いてくるホットループの中にいるとき |
Recursionのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なRecursionの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのRecursionのコード
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)JavaScriptでのRecursionのコード
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);JavaでのRecursionのコード
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}C++でのRecursionのコード
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}CでのRecursionのコード
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}再帰に関するよくある質問
再帰のベースケースとは何ですか？
それ以上再帰呼び出しをせずに答えられるほど小さい入力のことです。
fib(n) なら n <= 1 がそれにあたり、n をそのまま返します。到達可能なベースケースがなければ呼び出しは止まらず、スタックは伸び続け、プログラムはスタックオーバーフローでクラッシュします。呼び出しスタックとは何で、なぜ重要なのですか？
ランタイムは、開始したもののまだ返っていない呼び出しごとに1つのフレームを保持し、その引数とローカル変数を格納します。再帰の深さはそのままスタックの高さになるため、
n 段の深さまで再帰する処理は、各呼び出しがほとんど何もしなくても O(n) のメモリを使います。アニメーションの下に並ぶチップの列が、まさにこのスタックが伸びてほどける様子を示しています。再帰版フィボナッチはなぜ指数時間になるのですか？
同じ部分問題を何度も計算し直すからです。上の具体例では
fib(2) が fib(4) の中で2回評価されており、この重複はおよそ1段ごとに倍増して O(2^n) 回の呼び出しになります。最初に計算した結果をキャッシュする手法、すなわちメモ化を使えば、木は O(n) にまで畳み込まれます。再帰は反復より優れているのですか？
どちらかが常に優れているということはありません。あらゆる再帰は明示的なスタックを持つループに書き換えられますし、あらゆるループは再帰に書き換えられます。木の走査や 深さ優先探索 のような自己相似な問題では再帰が読みやすさで勝り、線形の処理ではメモリと呼び出しコストの面で反復が勝ります。
再帰関数でスタックオーバーフローが起きる原因は何ですか？
ベースケースが無いか到達できずに呼び出しが止まらないか、あるいは再帰自体は正しくても深さがランタイムのスタック上限に対して単純に大きすぎるか、のどちらかです。後者は、数百万件の入力に対して要素ごとに1回再帰するような場合です。対処法は、ベースケースへの到達を保証する、深さを抑える、反復に書き換える、のいずれかです。
関連リソース
その他の可視化
