Tower of Hanoi and recursion, explained simply

Written and play-tested by the Budi Games team · Updated August 2026

Three rods, a stack of discs in decreasing size, and one job: rebuild the stack on a different rod. The Tower of Hanoi is the smallest puzzle we know of that rewards you for thinking about a method instead of a move. Fiddle with the discs and you will get a four-disc tower across eventually. Learn the method and you will place seven discs without hesitating once, because every decision has already been made for you by the shape of the problem.

What follows is that method, the arithmetic behind it, and a shortcut that lets you solve the whole thing while barely paying attention. None of it requires algebra beyond doubling a number.

The rules, and the one that matters

There are three rules. You move one disc at a time. You may only take the disc that is currently on top of a rod. And a disc may never come to rest on a smaller disc.

The first two rules just describe what a hand can physically do with a stack of rings. The third rule is the entire puzzle. Because a big disc cannot sit on a small one, every disc you move has to land either on bare rod or on something larger than itself, and that single restriction is what forces you to shuffle small discs out of the way over and over again.

One consequence is worth stating early, because it dissolves most of the confusion beginners feel. The largest disc can only move when the rod it is leaving holds nothing above it and the rod it is going to holds nothing at all. In other words, the moment the biggest disc moves, every other disc in the puzzle must be sitting in one neat pile on the third rod. There is no other arrangement that permits it. That fact is not a strategy you invented — it is a logical requirement, and it hands you the plan.

The three-step plan that describes itself

Call the rod you start on the source, the rod you are aiming for the destination, and the remaining one the spare. To move a tower of n discs from source to destination:

1. Move the top n − 1 discs from the source to the spare rod.
2. Move the one remaining disc — the largest — from the source to the destination.
3. Move those n − 1 discs from the spare rod to the destination.

Read step one again. It asks you to move a tower of discs from one rod to another, which is exactly the problem you started with, only smaller by one disc. That is what recursion means: a description of a task that refers back to itself with a smaller input. The plan never tells you how to move n − 1 discs, and it does not have to, because the same three steps apply to them, and to the n − 2 inside those, all the way down to a single disc — which you simply pick up and put where it belongs.

The practical version at the table is quieter than the formal one. When it is time to shift a sub-tower, you do not need to plan its moves. You only need to remember three things: how many discs are in the sub-tower, where they are going, and which rod is temporarily the spare. Notice that the roles keep swapping. In step one the destination rod is acting as the spare; in step three the source rod is. Players who lose the thread almost always lose it there, by continuing to treat the original destination as sacred when for the moment it is just a parking space.

Why the minimum is exactly 2ⁿ − 1 moves

Let T(n) be the number of moves the plan takes for n discs. Step one costs T(n − 1), step two costs a single move, and step three costs T(n − 1) again. So T(n) = 2 · T(n − 1) + 1, and one disc obviously takes one move.

Unroll it and the pattern is immediate: 1, 3, 7, 15, 31, 63. Each line is double the previous line plus one, which is the same as saying each line is one short of a power of two. That gives the closed form 2ⁿ − 1.

These are not approximations and not our measurements. They are counts, and they are also a true minimum rather than merely what our plan happens to achieve. The argument for the minimum runs through the observation from earlier. The largest disc must move at least once, and just before it does, the other n − 1 discs must already be stacked together on the spare rod — which cost at least T(n − 1) moves. Afterwards they must all travel to the destination, costing at least T(n − 1) again. Two sub-solutions plus one move for the big disc: the lower bound and the plan agree, so the plan is optimal. There is nothing cleverer waiting to be discovered.

The doubling is what makes the puzzle feel deceptive. Adding one disc does not add a bit of work; it adds slightly more work than everything you have done so far. A six-disc solve is 63 moves. Seven is 127. If a friend watches you finish six and asks you to "just do one more", they have asked for twice the sitting.

The shortcut: watch the smallest disc

There is a second way to solve the tower that involves no planning at all, and it produces the same optimal sequence. It comes in two halves.

First: alternate. Every other move is a move of the smallest disc. In between, there is only ever one legal move that does not involve the smallest disc, so you make that one. You are never choosing; you are reading off the board.

Second: the smallest disc always travels in the same rotational direction, cycling through the three rods over and over, and which direction that is depends on the parity of the disc count. With an odd number of discs, the smallest disc's first hop goes to the destination rod, then to the spare, then back to the source, repeating. With an even number of discs it goes to the spare rod first, then the destination, then the source. We checked this against the recursive plan for every disc count from 1 to 12: same number of moves each time, 2ⁿ − 1, and the tower finishes on the destination rod in both cases.

The parity rule is easy to derive if you ever forget which way to start. Just ask where the smallest disc has to be at the very end of the first sub-tower. For three discs the top disc must end up above the second disc on the spare rod, and working backwards from there gives you the first hop. Or take the lazy route: make the first move, and if the position after four or five moves looks like it is building the wrong pile, restart with the other direction. Two discs are enough to test it.

Both methods matter for different reasons. The recursive plan is the one that teaches you something transferable. The alternating rule is the one that gets a ten-disc tower across the table while you hold a conversation.

Sixty-four discs, and the legend that shipped with the box

The puzzle was put on sale in 1883 by the French mathematician Édouard Lucas, under a pen name, and the box came with a story: in a temple, priests are moving 64 golden discs between three needles under the same rules, and when the last disc is placed, the world ends.

The story is not an ancient legend that Lucas discovered. It was written to sell the toy, and it worked so well that it is still repeated as folklore more than a century later. We think it is more interesting as an advertisement than it would be as a myth — someone in 1883 understood that a number most people cannot picture becomes memorable the instant you attach a deadline to it.

The number itself is honest. For 64 discs the minimum is 2⁶⁴ − 1, which is 18,446,744,073,709,551,615 moves. At one move every second, with no pauses, that is more than 580 billion years of moving discs — around 42 times the roughly 13.8 billion years since the Big Bang. The priests are safe, and so is everyone else.

That same number turns up in computing as the largest value a 64-bit unsigned integer can hold, which is not a coincidence: both are "one less than 2 to the 64th", because both are counting all the states of 64 binary things. The link runs deeper than a shared figure. Write the move number in binary and the bit that flips between one move and the next tells you exactly which disc moves — the smallest disc on every odd move, the second smallest every fourth move, and so on. Counting in binary and solving the tower are the same activity in different clothes.

What this actually teaches about recursion

Programmers meet the Tower of Hanoi early, usually as a five-line function, and the lesson is sometimes misread as "recursion makes hard problems easy". It does not. Recursion made the description short. The work is still 2ⁿ − 1 moves, and no rewriting will shrink it, because the lower bound is a property of the puzzle rather than of the code.

What recursion buys is that the description stays the same size as the problem grows. A plan for three discs and a plan for three hundred are the same three sentences. What it costs is that the plan keeps state you cannot see: at the deepest point of a large solve, you are holding n unfinished promises, each one waiting for a sub-tower to finish before it can move its own disc. That pile of promises is the call stack, and it is why doing it in your head stops being pleasant somewhere around six or seven discs. On the table you can cheat by reading the board instead of your memory, which is precisely what the alternating-disc rule lets you do.

Playing it here

Our Tower of Hanoi gives you three rods and a stack of discs, and it holds you to the rules — a disc will not settle on a smaller one, so an illegal attempt simply does not happen rather than punishing you for it. Because the exact minimum is known in advance, it is the rare puzzle where you can measure yourself against a perfect score instead of against another player: finish n discs in 2ⁿ − 1 moves and there is no better result.

A suggestion for your first sitting. Do three discs twice, slowly, and say the three steps out loud as you do them. Then do four without counting anything, just applying the plan. Then jump to six. Most players find the jump costs them nothing but time, and that is the moment the recursion has landed: the puzzle stopped getting harder and only got longer.

Questions players ask