1本目の棒にある円盤をすべて3本目の棒へ移す、定番のパズルです。ルールは2つだけ。円盤は1回に1枚ずつ動かすこと、そして小さい円盤の上に大きい円盤をのせないことです。
ハノイの塔は、1883年にフランスの数学者エドゥアール・リュカが考えたパズルです。64枚の円盤にまつわる伝説があり、1日1枚ずつ動かす僧侶たちが終えるには何千億年もかかるといわれます。円盤が1枚増えるたびに、必要な手数がほぼ2倍ずつ爆発的に増えていくからです。
棒をタップするといちばん上の円盤を持ち上げ、別の棒をタップするとそこに置きます。置けるのは、移す先の棒が空のときか、いちばん上の円盤が動かす円盤より大きいときだけです。
円盤がn枚のとき、理論上の最少手数は2ⁿ−1回です。大きな円盤を1枚動かすには、まずその上にのっている円盤をすべて別の棒へ移さなければなりません。このように、問題を「同じ形の、より小さな問題」に分けて解く工夫を、プログラミングでは再帰といいます。