JavaScript | 「再帰の動き」を図解で追う

では「再帰の動き」を図解で追ってみましょう。ここでは分かりやすい例として factorial(4) を使います。

コード

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

console.log(factorial(4));

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

console.log(factorial(4));

実行の流れ（潜っていく）

1. factorial(4)
   → 4 * factorial(3) を計算するために factorial(3) を呼ぶ
2. factorial(3)
   → 3 * factorial(2) を計算するために factorial(2) を呼ぶ
3. factorial(2)
   → 2 * factorial(1) を計算するために factorial(1) を呼ぶ
4. factorial(1)
   → 1 * factorial(0) を計算するために factorial(0) を呼ぶ
5. factorial(0)
   → 終了条件に当たり、1 を返す

戻りながら計算する流れ

• factorial(0) = 1
• factorial(1) = 1 * 1 = 1
• factorial(2) = 2 * 1 = 2
• factorial(3) = 3 * 2 = 6
• factorial(4) = 4 * 6 = 24

図でイメージ

factorial(4)
  → 4 * 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
factorial(4) = 4 * 6 = 24

ポイント

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