Up: Recursion. Next: Recursion.

In this puzzle, we have three pegs and several disks, initially stacked from largest to smallest on the left peg. (See the 6-disk picture below.) The rules are simple:

- Our goal is to move the entire tower to the middle peg.
- We can only move one disk at a time.
- We can never place a larger disk on a smaller one.

A 64-disk version of the puzzle lies in a Hanoi monastery, where monks work continuously toward solving the puzzle. When they complete the puzzle, the world will come to an end. This brings up two crucial questions on which the future depends:

- How should the monks solve the puzzle? That is, how can we write a program for solving the puzzle?
- If the monks use our program, how long will the world last?

To describe how the monks should solve this puzzle, the concept of recursion will be useful. We look at that next.

Next: Recursion.