Tower of Hanoi and recursion

The setup

Three rods. A stack of discs on the first, largest at the bottom. Move the whole stack to another rod, one disc at a time, taking only the top disc of a stack, and never placing a larger disc on a smaller one.

That is all of it. There is no hidden information and no luck. The interesting question is not whether it can be done, but how few moves it takes — and that has an exact answer.

The idea: to move n discs, move n − 1 twice

Think about the largest disc. It has to get from the first rod to the last at some point. For that to be legal, the rod it is going to must be completely empty, and it must have nothing on top of it — which means every other disc must be sitting on the third rod at that moment.

So the solution has a shape that is forced on you:

This is recursion in its purest form: the solution to the four-disc problem is the three-disc solution, one move, and the three-disc solution again. The three-disc solution is in turn two two-disc solutions with a move between them, and so on down to a single disc, which is just one move.

Why the count is 2ⁿ − 1

Write T(n) for the number of moves needed for n discs. The structure above says:

T(n) = T(n−1) + 1 + T(n−1) = 2 · T(n−1) + 1

with T(1) = 1. Each extra disc slightly more than doubles the work. Following it up:

• T(1) = 1
• T(2) = 3
• T(3) = 7
• T(4) = 15
• T(5) = 31, and by eight discs, T(8) = 255

Those are all one less than a power of two, and the pattern holds: T(n) = 2ⁿ − 1. The proof is a line — if T(n−1) = 2ⁿ⁻¹ − 1 then T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1.

It is also genuinely the minimum, not merely one option. The largest disc must move at least once, and for it to move at all the other n−1 discs must be stacked on a single rod beforehand and moved off afterwards. Those two operations cannot cost less than T(n−1) each, so nothing can beat 2ⁿ − 1.

The rule you can play without thinking

The recursive description is how you understand the puzzle. It is not how you play it, because keeping four levels of recursion in your head while clicking is unpleasant. There is a much simpler rule that produces exactly the same optimal sequence.

Number the discs by size, smallest as 1. Then alternate:

1. Every other move, move the smallest disc. Always in the same rotational direction, and never twice in a row.
2. On the moves in between, make the only other legal move there is. There is always exactly one, and it never involves the smallest disc.

The direction for the smallest disc depends on how many discs you have. With an odd number, keep cycling it towards your target rod; with an even number, cycle it the other way. Pick wrong and you will still solve it, just onto the wrong rod — which on a three-rod puzzle simply means you finish on the middle one.

That is the entire method. Alternate, never move the small disc twice, and take the forced move in between. It produces the shortest solution every time, for any number of discs.

Why this puzzle turns up in computing courses

Hanoi is the standard first example of recursion because the recursive solution is about four lines long and the iterative one is not obvious at all. Written out, it is close to the English description above: move the top n−1 to the spare rod, move the largest, move the n−1 across.

It is also the standard example of exponential growth being genuinely enormous. The legend attached to the puzzle involves sixty-four discs, which is 2⁶⁴ − 1 moves — over eighteen quintillion. At one move per second it takes something like five hundred and eighty billion years. Eight discs and two hundred and fifty-five clicks is the version we can offer.

Finally, it is a clean example of a problem where the shortest answer is provable. Most puzzles here can only tell you that you finished. This one can tell you whether you were perfect.