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.)

Hide comments

Comments

  • Allowed HTML tags: <em> <strong> <blockquote> <br> <p>

Plain text

  • No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.
Publish