ハノイの塔の可視化 — 再帰と最小手数 2ⁿ−1
ハノイの塔は、3本の棒と大きさの違う円盤を使うパズルです。ルールは「一度に1枚ずつ」「大きい円盤を小さい円盤の上に乗せない」の2つだけ。すべての円盤を A から C へ移します。このパズルは再帰——「大きな問題を、ひと回り小さい同じ問題に分けて解く」考え方の代表例で、最小手数はきっちり 2ⁿ−1 になります。1手ずつ動かして確かめてください。
いま何をしているか
再帰とは — 自分より小さい同じ問題に分ける
再帰とは、ある処理の中で自分自身（同じ手続き）を呼び出す解き方です。ポイントは、呼び出すたびに問題がひと回り小さくなり、いつか「これ以上分けられない最小のケース（ベースケース）」に行き着くこと。ハノイの塔は、この再帰の考え方がそのまま形になったパズルです。
ハノイの塔を再帰で解く
「n枚を A から C へ移す」を、こう分解します。
① 上の n−1 枚を、Cを作業場所にして A → B へ移す（これも同じ問題！）
② いちばん大きい n 枚目を A → C へ動かす
③ Bにある n−1 枚を、Aを作業場所にして B → C へ移す
①と③は「n−1枚を移す」というひと回り小さい同じ問題なので、また同じ手順で分解できます。これを繰り返し、「1枚を移す」まで小さくなれば、あとはそのまま動かすだけ。上の可視化の1手1手は、この分解を最後までたどった結果です。
最小手数は 2ⁿ−1
上の分解から、n枚に必要な手数は「（n−1枚の手数）＋1＋（n−1枚の手数）」。つまり1枚増えるごとに手数はほぼ倍になります。式で書くと最小手数は 2ⁿ − 1。3枚なら7手、10枚なら1023手、64枚ならおよそ1844京手——1枚増えるだけで爆発的に増える、これが指数的な増え方（O(2ⁿ)）です。円盤の枚数を変えて、手数がどう跳ね上がるか見てください。
つまずきやすいポイント
再帰には必ず「終わり（ベースケース）」がいる。 「小さい問題に分ける」だけでは、いつまでも自分を呼び続けて止まりません。ハノイなら「0枚（動かすものがない）」が終わりの合図です。プログラムの再帰でベースケースを書き忘れると、呼び出しが無限に積み上がってスタックオーバーフロー（コールスタックがあふれる）で止まります。
再帰の裏側では「コールスタック」が動いている。 関数が自分を呼ぶたび、戻り先がスタックに積まれ、終わると積んだ逆順に戻っていきます。これは スタック（LIFO） そのものの動きです。「後に呼んだものから先に戻る」ので、①→②→③の順序が正しく保たれます。
手数が2ⁿ−1でも、賢い近道はない。 ハノイの塔は、ルールを守る限りこれ以上少ない手数では解けません。再帰は「短く書ける」考え方であって、「計算が速くなる」わけではない点に注意。分割の仕方によっては指数的に重くなることもあります。
🧩 関連する可視化：再帰の裏側で動く スタックとキュー、手数の増え方＝計算量は ソートアルゴリズム や 探索アルゴリズム で。同じ「小さい問題に分ける」発想の 2分探索木 もどうぞ。擬似言語での再帰トレースは 擬似言語ステッパー で。
基本情報技術者試験ではこう出る
「再帰関数の定義・トレース」「ハノイの塔の最小手数（→ 2ⁿ−1）」「再帰とスタック（コールスタック）の関係」「ベースケースがないと止まらない」が定番です。小さい同じ問題に分ける・終わり（ベースケース）が要る・裏でスタックが動くの3点を、上の可視化と手数の変化で押さえておきましょう。関連：データ構造 ／ 計算量とO記法 ／ 可視化一覧。