How to solve the Tower of Hanoi, and why it teaches recursion

The rules

There are three pegs and a stack of discs, largest at the bottom. The goal is to move the whole stack from the left peg to the right peg. You may move only one disc at a time, only the top disc of a stack can move, and a disc may never sit on top of a smaller one.

That is the entire puzzle. The difficulty comes from the third rule: to get the biggest disc across, every other disc has to be out of the way, stacked in order, on the one peg you are not using.

The three-step solution that works for any size

Call the pegs Start, Spare and Target. To move a tower of n discs from Start to Target, do three things. First, move the top n - 1 discs from Start to Spare, using Target as the helper. Second, move the one remaining disc, the biggest, from Start to Target. Third, move the n - 1 discs from Spare onto Target, using Start as the helper.

Steps one and three are the same puzzle again, just smaller and between different pegs. You solve them with the same three steps, which call for a tower one disc smaller still, and so on down to a single disc, which you simply move. A method that solves a problem by using itself on a smaller version of the same problem is called recursion.

• Move the top n - 1 discs out of the way, onto the spare peg
• Move the biggest disc to the target peg
• Move the n - 1 discs back on top of it

Why it takes 2^n - 1 moves

Moving n discs costs two moves of n - 1 discs plus one move for the biggest disc. One disc takes 1 move, so two discs take 1 + 1 + 1 = 3, three discs take 3 + 1 + 3 = 7, four take 15, and each extra disc roughly doubles the work. The pattern is always one less than a power of two: 2^n - 1.

Nothing can beat it. The biggest disc has to move at least once, and before it can, every other disc must be stacked on the spare peg, which already costs the full solution for n - 1 discs. That is why the Tower of Hanoi counts your moves against 2^n - 1: it is a proven minimum, not a target someone picked.

The by-hand pattern

Recursion is how a computer thinks about the puzzle, but there is also a pattern you can follow without keeping track of anything. Imagine the three pegs in a circle. On every odd-numbered move, move the smallest disc one peg around the circle, always in the same direction: to the right if the number of discs is even, to the left if it is odd. On every even-numbered move, make the only legal move that does not touch the smallest disc.

Follow those two rules and the tower rebuilds itself on the target peg in the minimum number of moves, whatever its size.

The legend of the 64 golden discs

The puzzle was published in 1883 by the French mathematician Edouard Lucas, who sold it with a story: somewhere, monks are moving a tower of 64 golden discs, and when they finish, the world will end. The maths makes the story safe. 64 discs need 2^64 - 1 moves, about 18.4 quintillion, and at one move per second that would take roughly 585 billion years.

It is a vivid way to see exponential growth. Adding one disc doubles the time, so a problem that is easy at 3 discs becomes impossible at 64. The same doubling is why computer scientists care so much about how an algorithm's work grows as its input gets bigger.

Where recursion shows up in real computing

Folders inside folders are recursive: to count every file on a drive, count the files in a folder, then do the same for each folder inside it. Fast sorting methods such as merge sort split a list in half, sort each half the same way, then merge them. Fractal art, the way a web page is built from nested elements, and many game AIs that look moves ahead all work the same way.