Recursion, Explained with the Tower of Hanoi

A recursive function is one that calls itself. That sounds like a recipe for going round in circles, and it would be, except for one condition: each call works on a smaller version of the problem, and the smallest version is answered directly. This page explains recursion using the puzzle programmers have used to teach it for decades, and lets you watch a recursive program run.

Two parts: the base case and the recursive case

Every recursive function has the same two parts. Here is the classic small example, factorial, in Python:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

• The base case is an input simple enough to answer without recursion. Here it is n == 0, and the answer is 1.
• The recursive case answers every other input by calling the function on a smaller input — here n - 1 — and using the result.

The recursive case has to move towards the base case. factorial(4) calls factorial(3), which calls factorial(2), and so on down to factorial(0), which finally returns. Then each waiting call finishes its multiplication, in reverse order, and the answer climbs back up.

Factorial is a good first example, and a slightly misleading one: it is really just a loop wearing recursion’s clothes. A for loop multiplying 1 × 2 × 3 × 4 is just as clear. The Tower of Hanoi is different.

The leap of faith

The Tower of Hanoi asks you to move a stack of n disks from tower A to tower C, one disk at a time, never putting a larger disk on a smaller one. Try to plan that move by move and it becomes hopeless quickly: ten disks is 1,023 moves.

Recursion lets you skip the planning. Instead, assume you already know how to move a smaller stack. If some function can move n − 1 disks from any tower to any other, then moving n disks is easy:

1. Move the top n − 1 disks from A to B, out of the way.
2. Move the largest disk from A to C.
3. Move the n − 1 disks from B onto C.

Steps 1 and 3 are the same problem with one fewer disk, so the function can call itself for them. And the base case is the smallest stack of all: zero disks, where there is nothing to do. That is the whole program.

The unsettling part is step 1: how can a function use itself before it is finished being written? This is called the recursive leap of faith. You do not trace what the smaller call does; you trust that it does its job, and check only two things: that the base case is right, and that if the smaller calls work, this call works. That is exactly the shape of a proof by induction — and on the algorithm page it is the proof that the program is correct.

Watching it run

Faith is easier with evidence. Here is the program in Python, running for three disks. Step through it and watch three things: the highlighted line, the board, and the call stack — the list of calls that have started and not yet finished.

def hanoi(n, source, target, spare):
    """Move n disks from source to target, using spare as working space."""
    if n == 0:
        return
    hanoi(n - 1, source, spare, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, spare, target, source)


if __name__ == "__main__":
    hanoi(3, "A", "C", "B")

A few things only become visible when you can watch:

• Every call has its own variables. hanoi(3, "A", "C", "B") and the hanoi(2, "A", "B", "C") it calls both have an n, a source, a target and a spare, and they are different values. That is why the tower labels change as the stack grows: tower B is the spare for the first call and the target for the second.
• A call waits. When hanoi(3, …) calls hanoi(2, …), it stops on that line until the call it made has returned. The stack is the list of calls waiting like this.
• The stack stays shallow. The program makes fifteen calls for three disks, but never has more than four on the stack at once: a call finishes before its sibling starts.
• The base case does real work. Half of those fifteen calls are for zero disks and return immediately. They are what stop the recursion.

Why this puzzle, and not factorial

Factorial makes one recursive call, so its calls form a single chain. The Tower of Hanoi makes two, so its calls form a tree: each call on n disks branches into two calls on n − 1. That is the shape of most problems where recursion genuinely earns its place — searching a folder of folders, parsing nested brackets, sorting by splitting a list in halves — and Tower of Hanoi is the smallest honest example of it.

It is also a problem where the recursive solution is dramatically easier to find than any other. There is a way to solve it with a plain loop, and it is elegant — the iterative solution — but nobody would discover it without first seeing the recursive one. The recursion follows from the puzzle in two sentences.

Mistakes that break recursion

No base case, or one the calls never reach. Without a stopping point, a function calls itself until the call stack runs out and the program crashes — a RecursionError in Python, a StackOverflowError in Java. The quieter version of the same bug is a base case the input skips over: if the program reduced by n - 2 instead of n - 1, an odd n would jump straight past n == 0 into the negative numbers and never stop.

Arguments in the wrong order. In the first recursive call the target and spare swap places: hanoi(n - 1, source, spare, target). Write hanoi(n - 1, source, target, spare) by mistake and the smaller disks pile up on the target tower — exactly where the largest disk needs to go next — and the program prints an illegal move. The code still looks recursive, and still looks almost right, which is what makes this the most common Tower of Hanoi bug.

Work in the wrong place. The move has to happen between the two recursive calls. Print it before the first call and the program tries to move the largest disk while the others are still on top of it.

Repeating work without noticing. The naive recursive Fibonacci function calls itself twice, like Tower of Hanoi, and takes exponential time — but it gets there by computing the same values over and over, which remembering earlier results fixes. The Tower of Hanoi’s exponential running time is not like that: every one of its 2ⁿ − 1 moves is different and has to be made, and no solution can be shorter.

Recursion or a loop?

Anything recursive can be written as a loop, if necessary by keeping your own stack of unfinished work — the Java page does exactly that for the Tower of Hanoi. The question is which is clearer. When a problem contains smaller copies of itself, recursion usually is: the code mirrors the problem, and the proof that it works mirrors the code.

Loops win when the recursion would be very deep, since every language limits the call stack, and in languages that do not optimise tail calls — Python and Java among them — a recursive loop over a million items will fail where a for loop will not. The Tower of Hanoi is never in that danger. Its recursion is only as deep as the number of disks, and it runs out of time long before it could run out of stack.

To see the same function in other languages, with each one’s quirks, start at the Tower of Hanoi algorithm.

Frequently asked questions

Keep reading

• The History of the Tower of HanoiÉdouard Lucas, the 1883 puzzle sold under a false name, the legend of the sixty-four golden disks, and what the puzzle went on to become.
• Why the Minimum Is 2ⁿ − 1 MovesThe full proof that 2ⁿ − 1 moves is both achievable and unbeatable, why the shortest solution is unique, and how the moves divide between the disks.
• Tower of Hanoi, Binary and Gray CodeWhich disk moves on any move, read straight off the binary digits of the move number — and the Gray code that changes exactly the same bit.
• The Iterative Tower of Hanoi SolutionSolving the puzzle with a loop and two rules, and why those rules reproduce the recursive solution move for move.
• The Tower of Hanoi algorithmThe recursive solution running line by line, its proof, and its complexity — in pseudocode and six languages.