Up: Recursion. Next: Recursion.

About the Towers of Hanoi

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:

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

If JavaScript 1.2 is enabled on your browser, you can try it yourself. Just click on the disk you want to move, and then click on the peg you want to put it at. Although technically you are only allowed to move one disk at a time, the program will move several disks if it is necessary to complete the move.

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.