再帰とは（全体像）
再帰は、関数の中で自分自身をもう一度呼ぶ書き方。「大きな問題」を「ひとまわり小さい同じ問題」に置きかえていき、最後にいちばん小さいところで答えを確定する。
そのために2つの要素が必要だ。
- 基底条件 … これ以上分けられない最小のケース（ここで止まる）。
- 再帰呼び出し … 自分自身を、より小さな問題で呼ぶ。
いちばん大事なのは、基底条件がないと止まらないこと。終わりの条件がなければ自分を呼び続け、メモリを使い切ってスタックオーバーフロー（あふれ）で止まってしまう。だから基底条件は必須だ。
詳しく：基底条件・末尾再帰・メモ化だけ覚えれば戦える
ここが記事の心臓部。まずは再帰の2要素。
再帰の必須要素
| 要素 | 役割 |
|---|---|
| 基底条件 | これ以上分けない最小ケース（止まる条件） |
| 再帰呼び出し | より小さな問題で自分自身を呼ぶ |
たとえば階乗（1からnまでの掛け算）は、「n×（n−1の階乗）」と自分を呼び、最後に「0の階乗＝1」という基底条件で止まる。基底条件を書き忘れると止まらないので、ここが最大の注意点だ。
次に、よく問われる末尾再帰とメモ化。
末尾再帰とメモ化
| 用語 | 内容 |
|---|---|
| 末尾再帰 | 自分の呼び出しが処理の「最後」にある形。ループに最適化できる |
| メモ化 | 計算した結果を保存し、同じ計算を再利用する |
末尾再帰は、再帰呼び出しが処理のいちばん最後にある形。これは一部の言語でループに置きかえて最適化でき、メモリを節約できる（だから「再帰は反復より必ず遅い」とは限らない）。
メモ化は、一度計算した答えを覚えておいて使い回すこと。たとえばフィボナッチ数列を素朴に再帰で計算すると、同じ計算を何度も繰り返してO(2^n)と爆発的に遅くなる。メモ化すればO(n)まで速くなる。つまり、一度出した答えをメモして再計算を省くのがメモ化のねらい、というわけだね。
わかりやすく言い換えると
要するに、再帰は「マトリョーシカ人形」だ。
①再帰呼び出し … 人形を開けると、中にひとまわり小さい同じ人形が入っている
②基底条件 … いちばん小さい人形（もう開かない）。ここで止まる
基底条件を書き忘れるのは「いつまでも人形が出てくる」状態で、止まらずにあふれてしまう（スタックオーバーフロー）。
メモ化は「一度出した答えをメモ帳に控えておく」こと。同じ問いが来たら、計算し直さずメモを見るだけ。だからフィボナッチのようなむだな繰り返しが消えて速くなる、というわけだね。
試験のツボ
🔴 一番出る：基底条件が必須
①基底条件＝これ以上分けない最小ケース（止まる条件）
②書き忘れると止まらず、スタックオーバーフローになる
🔴 次に出る：末尾再帰とメモ化
①末尾再帰＝呼び出しが処理の最後にある形。ループに最適化できる
②メモ化＝計算結果を使い回す（フィボナッチがO(2^n)→O(n)）
🟡 押さえると安定：再帰の速さ
①「再帰は反復より必ず遅い」とは限らない
②末尾再帰の最適化やメモ化で速くできる
よくある間違い
①「再帰には基底条件がなくても問題なく動く」→ ✗ 基底条件がないと止まらず、スタックオーバーフローになる。必須。
②「再帰は反復（ループ）より必ず遅い」→ ✗ 末尾再帰はループに最適化でき、同等の速さになりうる。
③「メモ化をしてもフィボナッチの計算量は変わらない」→ ✗ 素朴な再帰のO(2^n)が、メモ化でO(n)まで速くなる。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（基底条件）
再帰の基底条件に関する次の記述のうち、正しいものはどれか。
- 基底条件は処理を速くするための工夫であり、なくても再帰は正しく止まる
- 基底条件は計算結果を保存するしくみで、書かなくても問題は起きない
- 基底条件は止まる条件で、ないと止まらずスタックオーバーフローになる
- 基底条件は再帰には不要で、ループにだけ必要となる条件のことである
解答は 3 だよ。
基底条件はこれ以上分けない最小ケース（止まる条件）で、これがないと再帰が止まらずスタックオーバーフローになるんだ。だから必須だよ。
選択肢1は「なくても止まる」が誤り。選択肢2は「計算結果を保存」でメモ化と取り違え。選択肢4は「再帰に不要」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | なければ止まらない |
| 2 | ✗ | それはメモ化の説明 |
| 3 | ✓ | 止まる条件・ないとSOFになる |
| 4 | ✗ | 再帰に必須 |
オリジナル問題2（メモ化）
メモ化に関する次の記述のうち、正しいものはどれか。
- 計算結果を保存して使い回し、フィボナッチをO(2^n)からO(n)に速める
- 計算結果を毎回すべて捨てるしくみで、計算量はかえって増えるものである
- メモ化は再帰を必ず無限ループにする、避けるべきとても危険な手法のことである
- メモ化をしてもフィボナッチの計算量は変わらず、O(2^n)のままである
解答は 1 だよ。
メモ化は計算結果を保存して使い回すことで、むだな再計算を消すんだ。素朴な再帰だとO(2^n)で爆発するフィボナッチが、メモ化でO(n)まで速くなるよ。
選択肢2は「毎回捨てる・増える」が誤り。選択肢3は「無限ループにする危険」が誤り。選択肢4は「変わらない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 結果を使い回しO(2^n)→O(n) |
| 2 | ✗ | 捨てずに保存して使い回す |
| 3 | ✗ | 無限ループにはしない |
| 4 | ✗ | メモ化で速くなる |
オリジナル問題3（末尾再帰）
末尾再帰に関する次の記述のうち、正しいものはどれか。
- 末尾再帰は基底条件を不要にするしくみで、止まる条件を書かなくてよい
- 末尾再帰は呼び出しが処理の最後にある形で、ループへと最適化できる
- 末尾再帰は必ず反復（ループ）より遅くなる、避けるべき書き方である
- 末尾再帰は計算結果を保存するしくみで、メモ化とまったく同じものだ
解答は 2 だよ。
末尾再帰は自分の呼び出しが処理の最後にある形で、一部の言語ではループに最適化できるんだ。だからメモリを節約でき、「再帰は必ず遅い」とは限らないよ。
選択肢1は「基底条件を不要にする」が誤り（基底条件は必要）。選択肢3は「必ず遅い」が誤り。選択肢4は「メモ化と同じ」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 基底条件は必要 |
| 2 | ✓ | 呼び出しが最後・ループに最適化できる |
| 3 | ✗ | 最適化で同等になりうる |
| 4 | ✗ | メモ化とは別もの |
まとめ
押さえどころ
- 🔴 基底条件 ＝ 止まる条件（最小ケース）。ないと止まらずスタックオーバーフロー。必須。
- 🔴 末尾再帰とメモ化 ＝ 末尾再帰はループに最適化できる。メモ化は計算結果を使い回す（フィボナッチO(2^n)→O(n)）。
- 🟡 再帰の速さ ＝ 「再帰は反復より必ず遅い」とは限らない。末尾再帰やメモ化で速くできる。
次に学ぶ
- スタック・キュー ── 再帰の呼び出しを支える「コールスタック」の正体。なぜ深い再帰でスタックがあふれるのかが分かる。
- 動的計画法（DP） ── メモ化を発展させた、むだのない計算の考え方。再帰の次のステップとして押さえたい。
執筆: SikakuQuest編集部