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.

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:

We'll answer both of these questions in sequence.

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

Next: Recursion.