JavaScript | 再帰とループの性能比較

JavaScript

2025.11.01

では「ハノイの塔」を題材に、再帰の美しさを図解で追ってみましょう。これは再帰アルゴリズムの代表的なパズルです。

ハノイの塔のルール
再帰的な考え方
コード例（JavaScript）
実行の流れ（3枚の場合）
図でイメージ（3枚）
✅ ポイント

ハノイの塔のルール

3本の棒（A, B, C）がある
大小の円盤を棒Aに大きい順に積んでおく
ルール:
1. 1回に動かせるのは1枚だけ
2. 大きい円盤の上に小さい円盤を置いてはいけない
目標: 棒Aの円盤をすべて棒Cに移す

再帰的な考え方

「n枚の円盤をAからCに移す」＝

n-1枚をAからBに移す（Cを補助に使う）
一番大きい円盤をAからCに移す
n-1枚をBからCに移す（Aを補助に使う）

コード例（JavaScript）

function hanoi(n, from, to, aux) {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  hanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  hanoi(n - 1, aux, to, from);
}

hanoi(3, "A", "C", "B");

function hanoi(n, from, to, aux) {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  hanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  hanoi(n - 1, aux, to, from);
}

hanoi(3, "A", "C", "B");

HTML

実行の流れ（3枚の場合）

hanoi(3, A, C, B)
- hanoi(2, A, B, C)
  - hanoi(1, A, C, B) → Move 1: A → C
  - Move 2: A → B
  - hanoi(1, C, B, A) → Move 3: C → B
- Move 4: A → C
- hanoi(2, B, C, A)
  - hanoi(1, B, A, C) → Move 5: B → A
  - Move 6: B → C
  - hanoi(1, A, C, B) → Move 7: A → C

図でイメージ（3枚）

Step 1: Move disk 1 A → C
Step 2: Move disk 2 A → B
Step 3: Move disk 1 C → B
Step 4: Move disk 3 A → C
Step 5: Move disk 1 B → A
Step 6: Move disk 2 B → C
Step 7: Move disk 1 A → C

👉 7手で解ける（一般に n 枚なら 2^n – 1 手）。