再帰関数の例としてよくハノイの塔のプログラムが紹介されます。 十進BASIC ＞ 十進BASIC＿パズル＆クイズ ＞ ハノイの塔の解法　にある十進BASIC のプログラムをそのまま JavaScript に移植しました。 ところが、 皿の数に関して小細工をしないと正常に作動しないのです。 なぜなの？

　 大きさの異なる相似形をした皿が ｎ枚 あります。 皿の直径は等比数列になっています。 それらは全て、 地点１ に重ね置かれています。 上に行くほど小さな皿になるようにして。 皿を置くことのできる地点には 地点１ の他に 地点２ と 地点３ があります。 そこで、 他の皿に触れることなく１枚ずつ皿を移動させて、 同じ地点に置かれた皿は必ず上に行くほど小さくなるように重ねていき、 地点１ に重ね置かれていた皿をすべて 地点２ に移動させるには、 最小で何回皿を移動させなければならないでしょうか？

皿の数？ 　　

　 上記のプログラムに似ていますが、 別のプログラムもあります。

皿の数？ 　　


手数は　 手です。　　　　ちなみに、 ２の乗 − １ ＝

　　　　　 参照 ：　ゼロからわかるJavaScript超入門　河西朝雄　著 （ 技術評論社 ）

　 ｎ 枚の皿からなるハノイの塔を移動させるには最低 ２ ⁿ−１ 回 の手技が必要です。
それを導いてみましょう。
　　　　１ 番大きな皿の移動回数 ：　１ 回
　　　　２ 番目に大きな皿の移動回数 ：　２ 回
　　　　３ 番目に大きな皿の移動回数 ：　２ ² 回
　　　　４ 番目に大きな皿の移動回数 ：　２ ³ 回
　　　　　　　　　　　・
　　　　　　　　　　　・
　　　　１ 番小さな皿の移動回数 ：　２ ⁿ⁻¹ 回

したがって、
　　　　１ ＋ ２ ＋ ２ ² ＋ ２ ³ ＋ ・ ・ ・ ＋ ２ ⁿ⁻¹
　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　（ 等比数列の和の公式より ）

　　　　　※　参照 ：　確率と統計学 ＞ ハノイの塔の漸化式