computer science goes bonk / all posts / rss / about

worth 1000 lines of code

While heading into work earlier this week, I became convinced that the classic recursive solution to the "Towers of Hanoi" problem couldn't possibly work.

Turns out I had the algorithm upside-down, a fact I realized once I got to work and drew a picture of the algorithm on a whiteboard.

Now I happen to like pictures. Being able to actually see a problem helps me organize my thoughts and figure out what should happen next. But as people drifted by and saw this piece of dry-erase resistance, it became clear that this approach doesn't work for everyone.

Refresher

In case you've forgotten, the Towers of Hanoi problems consists of N discs on three pegs:

start of game

The goal of the problem is to move all N discs from one peg to another (for example, from peg 0 to peg 2):

the goal of the game

There are only two rules:

  • You can only move one disc at a time
  • You can't put a bigger disc on top of a smaller disc

A Picture of a Photograph

There are iterative ways to solve this problem. Since my brain's stack pointer is easily corrupted, my usual style of play involves making random moves until I accidentally win. However, if you have more reliable storage, Towers of Hanoi practically begs to be solved recursively.

But first, go and see if you can remember how to do it. I'll wait here. Srsly. The internet isn't going anywhere.

Done?

Okay. Remember that thinking recursively involves breaking a problem into smaller versions of the same problem. For Towers of Hanoi, let's assume that we know how to solve the smaller problem that only involves N-1 discs:

  • Use the power of recursion to move the top N-1 discs to a temporary peg:

step one: get a box

  • Move the bottom disc to its final position:

step2

  • Harness once more the power of recursion to move the N-1 discs to their final position on top of the bottom disc:

step3

That's pretty much it. (Of course with any recursive algorithm, you have to know when to stop -- for Towers of Hanoi, the base case is 1 disc, which you can easily move.)