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

では「ハノイの塔の手数の一般式」を導きましょう。ここでは 再帰的な考え方と数学的帰納法を組み合わせて証明していきます。

再帰的な手数の式

• ( T(n) ) = n枚の円盤を移動するのに必要な最小手数
• 再帰的な手順は：
  1. ( n-1 ) 枚を補助棒に移す → ( T(n-1) ) 手
  2. 最大の円盤を移す → 1手
  3. ( n-1 ) 枚をゴール棒に移す → ( T(n-1) ) 手

したがって： [ T(n) = 2T(n-1) + 1 ]

基本ケース

• ( T(1) = 1 ) （1枚なら1手で移せる）

帰納的な展開

• ( T(2) = 2T(1) + 1 = 2 \cdot 1 + 1 = 3 )
• ( T(3) = 2T(2) + 1 = 2 \cdot 3 + 1 = 7 )
• ( T(4) = 2T(3) + 1 = 2 \cdot 7 + 1 = 15 )

パターンが見えてきますね：
[ T(n) = 2^n – 1 ]

数学的帰納法による証明

1. 基底部
   • ( n=1 ) のとき、( T(1) = 1 )
   • 一方、( 2^1 – 1 = 1 )
   • よって成り立つ。
2. 帰納法の仮定
   • ( T(k) = 2^k – 1 ) が成り立つと仮定する。
3. 帰納法のステップ
   • ( T(k+1) = 2T(k) + 1 )
   • 仮定を代入すると：
     [ T(k+1) = 2(2^k – 1) + 1 = 2^{k+1} – 2 + 1 = 2^{k+1} – 1 ]
4. 結論
   • よってすべての自然数 ( n ) に対して
     [ T(n) = 2^n – 1 ]
     が成り立つ。

✅ ポイント

• ハノイの塔は「再帰的な定義」から「指数関数的な成長」が自然に導かれる。
• 枚数が増えると手数は爆発的に増える（例: 64枚なら (2^{64}-1) 手 ≈ 1.8×10^19 手）。
• これが「再帰的思考」と「数学的帰納法」の美しい融合例。

👉 ここまでで「ハノイの塔の一般式」を証明できました。