Using Recursion to Solve the Hanoi Towers Puzzle

An example of a recursive algorithm that doesn't have a simple, intuitive, nonrecursive solution is a puzzle called Hanoi Towers: You place 64 rings on a tower in descending order by size (largest to smallest). Then, you move these 64 rings to a second tower by using a third tower. Only one ring can move at a time, and you aren't allowed to place a ring on top of a smaller ring. You can use a classic recursive solution for this problem. To move n rings from tower 1 to tower 2, where n is the number of rings that need to be moved (in this case, 64) move n-1 rings from tower 1 to tower 3. Then, move ring n from tower 1 to tower 2; move n-1 rings from tower 3 to tower 2.

You know how to move a single ring from one tower to another. But how do you move n-1 rings from tower 1 to tower 3? Use recursion! Move n-2 rings from tower 1 to tower 2; move ring n-1 from tower 1 to tower 3; move n-2 rings from tower 2 to tower 3, and so on. Your task is finished when you've placed all the rings on tower 2.

Although I found a nonrecursive algorithm to solve this problem, the solution is far from intuitive and requires mathematical proofs. (For more information about recursion, see Jeffrey Bane, "The Zen of Recursion," page 59.)