再帰

何がうれしい？

ループ（反復）でも同じことはたいてい書けます。それでも再帰が好まれるのは、「全体は部分の繰り返しでできている」構造を、そのままコードに写し取れるからです。

• 木構造の探索（ファイルのフォルダ、HTML/DOM、JSON）— 「フォルダの中身を処理する」関数が、サブフォルダに対して自分を呼ぶ
• 分割統治（クイックソート、マージソート、二分探索）— 半分に分けて、それぞれを同じ手順で解く
• 数学的な定義がそのまま再帰（階乗、フィボナッチ、ユークリッドの互除法）

「問題の中に、同じ形の小さい問題が入れ子になっている」と気づいたら、再帰の出番です。

再帰の2つの部品

再帰関数は、必ず次の2つから成り立ちます。どちらか一方でも欠けると、正しく動きません。

function factorial(n) {
  if (n === 0) return 1;        // ① ベースケース：ここで止まる
  return n * factorial(n - 1);  // ② 再帰ケース：1つ小さい問題を呼ぶ
}
factorial(5); // 120  →  5 × 4 × 3 × 2 × 1

ポイントは、再帰ケースが必ずベースケースに近づいていくこと。上の例では呼ぶたびに n が 1 ずつ減るので、いつか必ず 0（ベースケース）に到達します。

コールスタックとスタックオーバーフロー

再帰を理解するカギはコールスタックです。関数を呼ぶと、戻り先や途中の変数を記録した「スタックフレーム」が積み上がります。factorial(5) を呼ぶと、factorial(0) が答えを返すまで5個のフレームが積み重なったまま待機します。

factorial(5)  → 5 * factorial(4) を待つ
  factorial(4) → 4 * factorial(3) を待つ
    factorial(3) → 3 * factorial(2) を待つ
      factorial(2) → 2 * factorial(1) を待つ
        factorial(1) → 1 * factorial(0) を待つ
          factorial(0) → 1 を返す（ベースケース）
        ← 1 を返す  ← 2 を返す  ← 6 ... と巻き戻りながら計算

このスタックには容量の上限があります。再帰が深すぎる（＝フレームが積み上がりすぎる）と、上限を超えてスタックオーバーフローになります。

反復（ループ）との比較

同じ階乗をループで書くと、こうなります。スタックを積まないので、深さの心配がありません。

function factorial(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}

つまずきポイント：素朴なフィボナッチ

再帰の「うっかり」で有名なのが、フィボナッチ数列の素朴な実装です。定義をそのまま書けて美しいのですが、同じ計算を爆発的に繰り返します。

def fib(n):
    if n < 2:
        return n            # ベースケース：fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2)

fib(5) は fib(4) と fib(3) を呼び、その fib(4) がまた fib(3) を呼ぶ…と、同じ fib(3) を何度も計算します。計算量はおよそ O(2ⁿ) に膨らみ、fib(50) ですら現実的な時間で終わりません。

from functools import lru_cache

@lru_cache(maxsize=None)   # 計算結果を自動でキャッシュ（メモ化）
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

末尾再帰という最適化

再帰ケースで、自分自身の呼び出しが「最後の処理」になっている形を末尾再帰（tail recursion）と呼びます。最初の factorial は n * factorial(...) と、戻ってきた値に掛け算がまだ残るので末尾再帰ではありません。途中結果を引数で持ち回ると、末尾再帰に書き換えられます。

// 末尾再帰：return が「自分の呼び出しそのもの」で終わる
function factorial(n, acc = 1) {
  if (n === 0) return acc;
  return factorial(n - 1, acc * n); // 呼び出しの後にやることが無い
}

呼び出しの後にやることが無いため、コンパイラ/処理系は今のフレームを使い回して新しいフレームを積まずに済ませられます。これが**末尾呼び出し最適化（TCO）**で、うまく効けば深さが深くてもスタックを消費しません（ループ相当に変換される）。

まとめ：再帰を使う前のチェック

• ベースケースはあるか？ そして再帰ケースは毎回それに近づくか？
• 再帰の深さは入力サイズに比例して青天井にならないか？（なるならループ/明示スタックを検討）
• 同じ部分問題を重複して解いていないか？（出ているならメモ化）

再帰は「木構造・分割統治・数学的定義」を、人間の考え方そのままに書ける強力な道具です。一方でコールスタックという有限資源の上で動く点を忘れずに。ループと再帰は対立ではなく、問題の形に合うほうを選ぶのが正解です。