Towers of Hanoi

If you've gone through the tutorial on recursion, then you're ready to see another problem where recursing multiple times really helps. It's called the Towers of Hanoi. You are given a set of three pegs and $n$‍ disks, with each disk a different size. Let's name the pegs A, B, and C, and let's number the disks from 1, the smallest disk, to $n$‍, the largest disk. At the outset, all $n$‍ disks are on peg A, in order of decreasing size from bottom to top, so that disk $n$‍ is on the bottom and disk 1 is on the top. Here's what the Towers of Hanoi looks like for $n=5$‍ disks:

The goal is to move all $n$‍ disks from peg A to peg B:

Sounds easy, right? It's not quite so simple, because you have to obey two rules:

You might think that this problem is not terribly important. Au contraire! Legend has it that somewhere in Asia (Tibet, Vietnam, India—pick which legend on the Internet you like), monks are solving this problem with a set of 64 disks, and—so the story goes—the monks believe that once they finish moving all 64 disks from peg A to peg B according to the two rules, the world will end. If the monks are correct, should we be panicking in the streets?

First, let's see how to solve the problem recursively. We'll start with a really easy case: one disk, that is, $n=1$‍. The case of $n=1$‍ will be our base case. You can always move disk 1 from peg A to peg B, because you know that any disks below it must be larger. And there's nothing special about pegs A and B. You can move disk 1 from peg B to peg C if you like, or from peg C to peg A, or from any peg to any peg. Solving the Towers of Hanoi problem with one disk is trivial, and it requires moving only the one disk one time.

How about two disks? How do you solve the problem when $n=2$‍? You can do it in three steps. Here's what it looks like at the start:

First, move disk 1 from peg A to peg C:

Notice that we're using peg C as a spare peg, a place to put disk 1 so that we can get at disk 2. Now that disk 2—the bottommost disk—is exposed, move it to peg B:

Finally, move disk 1 from peg C to peg B:

This solution takes three steps, and once again there's nothing special about moving the two disks from peg A to peg B. You can move them from peg B to peg C by using peg A as the spare peg: move disk 1 from peg B to peg A, then move disk 2 from peg B to peg C, and finish by moving disk 1 from peg A to peg C. Do you agree that you can move disks 1 and 2 from any peg to any peg in three steps? (Say "yes.")

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.