ハノイの塔
「大きい円盤を小さい円盤の上に置けない」パズルを、再帰がどう解くかを見ます。
4
0
いまの手数
0
必要な総手数 2ⁿ−1
15
直前の移動
—
3 本の柱と、大きさの違う円盤。すべての円盤を別の柱へ移します。ルールは
1 回に 1 枚／大きい円盤を小さい円盤の上に置けない。
解き方は 再帰そのもの ── 「n 枚を A から C へ移す」は、
① 上の n−1 枚を A から B へ移す → ② 一番下の 1 枚を A から C へ → ③ n−1 枚を B から C へ移す。
「n−1 枚を移す」も同じやり方で解ける（より小さい同じ問題）。手数は必ず 2ⁿ−1 回になります。
解き方は 再帰そのもの ── 「n 枚を A から C へ移す」は、
① 上の n−1 枚を A から B へ移す → ② 一番下の 1 枚を A から C へ → ③ n−1 枚を B から C へ移す。
「n−1 枚を移す」も同じやり方で解ける（より小さい同じ問題）。手数は必ず 2ⁿ−1 回になります。
再帰の構造
hanoi(n, 始点, 終点, 経由):
hanoi(n−1, 始点, 経由, 終点) ← 上の n−1 枚をどける
円盤 n を 始点 → 終点 へ動かす
hanoi(n−1, 経由, 終点, 始点) ← n−1 枚を戻す
hanoi(n−1, 始点, 経由, 終点) ← 上の n−1 枚をどける
円盤 n を 始点 → 終点 へ動かす
hanoi(n−1, 経由, 終点, 始点) ← n−1 枚を戻す
いま何が起きている？
ここがポイント
- 大問題（n 枚）を 同じ形のより小さい問題（n−1 枚）に帰着 ── これが再帰。
- 総手数は
2ⁿ−1。n が 1 増えるごとに手数はほぼ 2 倍に増える（指数的）。 - 円盤 64 枚の伝説では 2⁶⁴−1 ≈ 1844 京手 ── 1 秒 1 手でも宇宙の年齢を超える。