ハノイの塔

再帰の説明に必ずといって良いほど持ち出される有名なパズルである。 3つの棒と直径が 1, 2, …, nの n枚の真中に穴のあいた円盤を用いる。

最初は、すべての円盤が、小さいものを上に大きさの順に 1つの棒にささっている。 そして、下のルールにしたがって、すべての円盤を別の一つの棒に移動したら、 終了である。

• 一度に 1枚の円盤だけを動かすことができる。
• 小さな円盤の上に大きな円盤をのせては行けない。

ハノイの塔は再帰法を使って解くことができる。つまり、まず 1枚の場合は解き方はわかっている。 次に n-1 枚の場合の解き方がわかっているとして、 n 枚を棒 Aから棒 Bへ移動する場合:

1. n-1 枚の円盤を棒 Aから棒 Cへ移動する。 このやり方はわかっている。
2. 一番下のもっとも大きな 1枚（円盤 n）を棒 Aから棒 Bへ移動する。
3. n-1 枚の円盤を再び棒 Cから棒 Bへ移動する。

プログラムとその実行の様子は下のアニメーションのようになる。