JavaScript | 再帰関数

では「再帰の動きを図解で追う」ステップに進みましょう。
例として factorial(3) を使います。

コード

function factorial(n) {
  if (n === 0) return 1;       // 終了条件
  return n * factorial(n - 1); // 再帰ステップ
}

console.log(factorial(3));

function factorial(n) {
  if (n === 0) return 1;       // 終了条件
  return n * factorial(n - 1); // 再帰ステップ
}

console.log(factorial(3));

実行の流れをステップごとに追う

1. 最初の呼び出し
   • factorial(3)
   • 終了条件ではないので → 3 * factorial(2) を計算するために factorial(2) を呼ぶ。
2. 2回目の呼び出し
   • factorial(2)
   • 終了条件ではないので → 2 * factorial(1) を計算するために factorial(1) を呼ぶ。
3. 3回目の呼び出し
   • factorial(1)
   • 終了条件ではないので → 1 * factorial(0) を計算するために factorial(0) を呼ぶ。
4. 4回目の呼び出し
   • factorial(0)
   • ここで終了条件に当たり、1 を返す。

戻りながら計算する流れ

• factorial(0) が 1 を返す
• factorial(1) = 1 * 1 = 1
• factorial(2) = 2 * 1 = 2
• factorial(3) = 3 * 2 = 6

図でイメージ

factorial(3)
  → 3 * factorial(2)
            ↓
            2 * factorial(1)
                    ↓
                    1 * factorial(0)
                            ↓
                            1 (終了条件)

戻りながら計算すると：

factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6

ポイント

• 再帰は「潜っていく」ときと「戻ってくる」ときの2段階がある。
• 潜るときは「まだ答えが出ないから次へ進む」。
• 戻るときに「答えが積み上がって完成する」。