1 歩ずつ動かす
- factorial(4)いま動いている
戻ってきた値まだ無い
これまでに戻った値 (返した順)
まだどの呼び出しも返していません。
- いま動いている呼び出し
- 戻りを待っている呼び出し
- 戻ってきた値
- 空いている枠
図の箱は、まだ答えを返していない呼び出しです。下から順に呼び、上から順に返します。
1 歩目 / 全 8 歩呼んだ回数 1 回積まれている呼び出し 1 個
factorial(4) を呼びます。積まれた呼び出しは 1 個です。
いま動いている疑似コードの行
- 1factorial(n)
- 2もし n == 1 なら
- 31 を返す (終わりの条件。ここで折り返す)
- 4r = factorial(n - 1) を呼んで待つ
- 5n × r を返す
見本を変える
予想してみる
いまは 1 歩目です。
次に呼ばれるのは、どれでしょう。
今回わかること
- 関数が自分を呼ぶたびに、呼び出しが上へ積み重なる流れ
- 終わりの条件で折り返し、値が逆の順で戻ってくる理由
前提
- 関数の呼び出しと return
- スタック (最後に積んだ物から出る)
どんな考え方か
再帰は、関数の中で同じ関数を呼び、問題を 1 つ小さくして解く考え方です。階乗なら、n の階乗は n × (n - 1 の階乗) と書けます。
小さくし続けると、いつか答えがすぐ分かる形に行き着きます。これを終わりの条件と呼びます。終わりの条件が無いと呼び出しが止まらず、積み重なりがあふれてエラーになります。
手順と具体例
- 1n が 1 なら、もう呼ばずに 1 を返す (終わりの条件)
- 2そうでなければ、factorial(n - 1) を呼び、答えが戻るまで待つ
- 3戻ってきた値に n をかけて返す
- 4返した呼び出しは積み重なりから外れ、1 つ下の呼び出しが続きを動かす
| 呼び出し | 中でしていること | 返す値 |
|---|---|---|
| factorial(4) | 4 × factorial(3) | 24 |
| factorial(3) | 3 × factorial(2) | 6 |
| factorial(2) | 2 × factorial(1) | 2 |
| factorial(1) | 終わりの条件。呼ばずに 1 を返す | 1 |
呼び出しの回数と計算量
| 数えるもの | 回数と量 | 計算量 |
|---|---|---|
| 呼び出しの回数 | n 回 | O(n) |
| かけ算の回数 | n - 1 回 | O(n) |
| いちばん高く積まれる数 | n 個 (その分のメモリを使う) | O(n) |
n が 6 なら 6 回呼び、いちばん深いところで 6 個積まれます。Python は既定で 1000 段ほど積むと RecursionError で止まるので、とても深い再帰は for 文に書き直します。
使いどころ
向いているとき
- 問題を同じ形の小さい問題に分けられるとき (階乗、フォルダの中のフォルダ)
- 木やグラフを深くたどるとき (深さ優先探索)
- 分けて解いてから合わせるとき (マージソート)
向いていないとき
- 何万段も深くなるとき (積み重なりがあふれる。for 文で書く)
- 同じ呼び出しを何度もくり返すとき (結果を覚えておく工夫が要る)
コード
疑似コード
- 1factorial(n)
- 2もし n == 1 なら
- 31 を返す (終わりの条件。ここで折り返す)
- 4r = factorial(n - 1) を呼んで待つ
- 5n × r を返す
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- 終わりの条件を書き忘れると、どうなりますか？
- factorial(0)、factorial(-1) と呼び出しが止まらずに積み重なり、やがてあふれます。Python では RecursionError、Java では StackOverflowError になります。
- スタックと何の関係がありますか？
- まだ返していない呼び出しは、スタックと同じく上に積まれ、最後に呼んだ物から返ります。この積み重なりを、呼び出しのスタックと呼びます。
- for 文で書くのと、どちらがよいですか？
- 階乗なら for 文のほうが速く、深さの心配もありません。再帰は、木のたどり方のように、分けて考えると読みやすくなる問題で使います。
