Recursion Through the Tower of Hanoi

Picture the steel tiffin stack your mother packs for a train journey — three boxes, largest at the bottom, smallest on top, each lid a little smaller than the one below it. Now imagine a strange rule: you must move the entire stack to a different bag, one box at a time, you may rest boxes only inside a bag (never on the table), and you can never place a bigger box on top of a smaller one. You are allowed to use one spare bag to help. How many box-moves does that take, and in what order? Try it in your head with just two boxes before reading on. You will find yourself doing something interesting: to move the bottom box, you first have to clear the box sitting on it — by moving that smaller box out of the way — then move the bottom box, then bring the smaller box back on top. You solved a 2-box problem by solving a 1-box problem twice, with one extra move in between. That instinctive move — solving a problem by solving a smaller version of the very same problem — is the entire idea of recursion, and this chapter builds it up rigorously using the oldest and clearest example computer science has: the Tower of Hanoi.

The Puzzle, Precisely Stated

The Tower of Hanoi consists of three upright pegs, which we will call A, B and C, and a set of circular discs of different sizes stacked on peg A in decreasing order of size — the largest disc at the bottom, the smallest at the top. The goal is to move the entire stack from peg A to peg C, following exactly three rules:

• Only one disc may be moved at a time.
• Each move takes the topmost disc from one peg and places it on top of another peg.
• A disc can never be placed on top of a smaller disc.

The puzzle was invented in 1883 by the French mathematician Édouard Lucas, who sold it with a marketing legend attached: somewhere in a temple at Kashi (Benares), the story goes, priests are moving 64 golden discs according to these very rules, and when they finish, the world will end. It is worth being clear that this is a legend Lucas invented to sell the toy — not a documented historical practice — but it turns out to be a wonderful way to feel the size of the number 2⁶⁴, which we will calculate honestly, without the legend, later in this chapter.

Starting Small: One and Two Discs

Before writing any code, solve the puzzle by hand for the smallest cases, because the pattern that emerges is exactly what recursion will later automate.

One disc: trivial. Pick it up from A, place it on C. That is one move.

Two discs (call them 1, the smaller, and 2, the larger, sitting with 2 at the bottom of peg A): You cannot move disc 2 first, because disc 1 is sitting on it, and you cannot move disc 2 onto disc 1 anywhere else either (that breaks the size rule immediately if you try). So the only productive first move is to get disc 1 out of the way — onto peg B, the spare. Now disc 2 is free; move it straight to peg C. Finally, bring disc 1 from B onto C, on top of disc 2. Total: three moves. Notice the shape of the solution: move the smaller stack out of the way, move the biggest disc, bring the smaller stack back on top.

Three discs is where doing it "by feel" starts to strain memory — most people who try it by hand without a system make a wrong move within the first four steps. That difficulty is precisely the motivation for building a systematic, repeatable procedure rather than relying on intuition. And the procedure we need is recursion.

What Recursion Actually Is

A recursive procedure is one that solves a problem by calling itself on a smaller version of the same problem, until the problem becomes so small that it can be answered directly without any further calls. That smallest, directly-answerable case is called the base case. Every other case, where the procedure calls itself, is called the recursive case. Every correct recursive procedure needs both parts: without a base case, the calls never stop; without a recursive case, it can only ever solve the smallest problem.

Here is the key mental trick, sometimes called the "recursive leap of faith": when you are designing the recursive case, you are allowed to assume that a call to the same procedure on a smaller input already works correctly — you do not need to trace it out in your head to trust it. Your only job at that level is to describe how to build the answer to the current problem using that assumed, already-solved smaller answer. This feels uncomfortable the first time you meet it, because it seems circular. It is not circular, because the input strictly shrinks on every call and the base case is guaranteed to be reached — we will prove that shrinking property is watertight when we look at the code.

Apply the leap of faith to Hanoi. Suppose you already trust that "move n-1 discs from any peg to any other peg, using the third as spare" works correctly, for some smaller number n-1. Then moving n discs from A to C using B as spare breaks into exactly three trusted steps:

1. Move the top n-1 discs from A to B, using C as the spare. (Trusted smaller call.)
2. Move the single remaining, largest disc directly from A to C. (One concrete move — the base case action.)
3. Move the n-1 discs from B to C, using A as the spare. (Trusted smaller call, again.)

That is the entire algorithm. It looks almost too simple, which is exactly the point of recursion done well: the hard-looking problem for n discs reduces to two copies of the identical problem for n-1 discs, plus one plain move in the middle.

Writing It as Code

Translate the three steps directly into a Python function. The function takes the number of discs to move and the names of the source peg, the spare (auxiliary) peg, and the target peg:

def hanoi(n, source, auxiliary, target):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, target, auxiliary)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, source, target)

hanoi(3, 'A', 'B', 'C')

Read this against the three steps above. The base case, n == 1, moves that single disc directly and returns — no further calls, which is what stops the recursion. The recursive case does exactly the three things we described: it calls hanoi(n - 1, source, target, auxiliary) to shift the top n-1 discs onto the auxiliary peg (notice the auxiliary and target arguments swap places here — the peg we called "spare" becomes the destination for this smaller sub-problem, and the real target becomes the spare for it); then it prints the one concrete move of the largest disc from source to target; then it calls hanoi(n - 1, auxiliary, source, target) to bring those n-1 discs from the auxiliary peg onto the target, now using the original source peg as the spare.

Notice that both recursive calls invoke the exact same function with the exact same logic — there is no special-case code for "the first half" versus "the second half" of the solution. Only the peg names passed as arguments change. This is worth stating explicitly because it is a common point of confusion.

Common Misconception: "The Two Halves Must Work Differently"

A very natural mistake is to think that moving the first batch of n-1 discs out of the way and moving them back afterward must require different code, since one happens "before" the big disc moves and the other "after." They do not. Both are literally the same sub-problem — move n-1 discs from one peg to another using the third as spare — just with different pegs plugged in as source, auxiliary and target. The recursive leap of faith means you write the logic for that sub-problem exactly once, and reuse it by relabeling which physical peg plays which role. If you ever find yourself writing separate logic for the "before" and "after" phases of a recursive solution, that is a signal you have not yet found the true recursive structure of the problem.

Tracing the Full Call for Three Discs

Trust is good; verification is better. Let us trace hanoi(3, 'A', 'B', 'C') completely, one call at a time, to see the recursion actually unwind into concrete moves, and to confirm the code truly produces a legal, complete solution rather than just claiming to.

The outer call hanoi(3, A, B, C) is a recursive case, since n = 3 ≠ 1. It first calls hanoi(2, A, C, B) — move 2 discs from A to B using C as spare. That call is itself a recursive case: it calls hanoi(1, A, B, C), which is a base case and prints "Move disk 1 from A to C" directly. Back in hanoi(2, A, C, B), it then prints "Move disk 2 from A to B", and finally calls hanoi(1, C, A, B), a base case, which prints "Move disk 1 from C to B". That completes hanoi(2, A, C, B) and returns control to the outer call, which prints "Move disk 3 from A to C" — the one big disc move sitting in the middle of the whole solution. The outer call then makes its second recursive call, hanoi(2, B, A, C), which by identical reasoning produces "Move disk 1 from B to A", "Move disk 2 from B to C", "Move disk 1 from A to C".

Reading the printed moves in the order they actually execute gives the complete, seven-move solution:

1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

You can check this is legal by walking through the peg contents yourself: start A = [3,2,1] (bottom to top), B = [], C = []. After move 1, A = [3,2], C = [1]. After move 2, A = [3], B = [2]. After move 3, C = [], B = [2,1]. After move 4, A = [], C = [3]. After move 5, B = [2], A = [1]. After move 6, B = [], C = [3,2]. After move 7, A = [], C = [3,2,1]. Every intermediate stack has larger discs below smaller ones, and the final state has all three discs on C in the correct order — the algorithm is verified, not just asserted.

The Diagram: Watching the Discs Move

Panel 1 is the starting stack on peg A. Panel 2 is the state right after the first recursive call finishes — the top two discs sit safely on peg B, exactly as the leap of faith promised. Panel 3 shows the single concrete move of disc 3, the biggest disc, sliding onto the now-empty peg C. Panel 4 shows the second recursive call finishing, bringing the two-disc stack from B onto C, completing the puzzle in seven moves.

How Many Moves, in General?

Let T(n) denote the number of moves needed for n discs. From the algorithm itself, solving for n discs requires solving for n-1 discs, then one move, then solving for n-1 discs again:

T(n) = 2 * T(n - 1) + 1,   with T(1) = 1

This kind of equation, where a quantity is defined using a smaller version of itself, is called a recurrence relation — it is the numeric twin of a recursive function, and it is worth noticing that the code and the recurrence have exactly the same shape. Compute the first few values directly: T(1) = 1. T(2) = 2(1) + 1 = 3. T(3) = 2(3) + 1 = 7, matching our hand trace exactly. T(4) = 2(7) + 1 = 15. T(5) = 2(15) + 1 = 31.

Look at the sequence: 1, 3, 7, 15, 31. Each term is one less than a power of 2: 2¹−1, 2²−1, 2³−1, 2⁴−1, 2⁵−1. The general formula is T(n) = 2n − 1, and you can confirm it satisfies the recurrence algebraically: if T(n-1) = 2n-1 − 1, then 2·T(n-1) + 1 = 2·(2n-1 − 1) + 1 = 2n − 2 + 1 = 2n − 1, which is exactly T(n). Since the formula also matches the base case T(1) = 21 − 1 = 1, it holds for every n.

Common Misconception: "More Discs Means Proportionally More Moves"

Students who have not yet met exponential growth often guess that doubling the number of discs roughly doubles the effort, or that the move count grows like n squared. The recurrence tells a very different story: each additional disc doubles the previous move count and adds one. That is exponential growth, not linear or quadratic growth, and the gap becomes enormous very quickly. Ten discs need 1,023 moves. Twenty discs need 1,048,575 moves. Now return to Lucas's legend of 64 golden discs, without any embellishment: 264 − 1 = 18,446,744,073,709,551,615 moves. At one move every second, day and night, that is roughly 585 billion years — more than forty times the current estimated age of the universe. No temple has been doing this; it is a story. But the arithmetic behind the story is completely real, and it is the cleanest demonstration available at this level of just how fast exponential quantities escape human intuition — a fact that matters far beyond puzzles, in anything from population growth to compound interest to the difficulty of cracking long passwords.

Recursion Depth Versus Total Calls

Every time hanoi calls itself, Python must remember where to resume the outer call once the inner one finishes — it keeps a record, called a stack frame, for each call that is currently waiting. The maximum number of these waiting frames at any single moment is called the recursion depth. For our 3-disc example, the deepest chain is hanoi(3,…) waiting on hanoi(2,…) waiting on hanoi(1,…) — three frames, matching n exactly. In general, the recursion depth for Hanoi is simply n, because each level of nesting reduces the disc count by exactly one before making its next call.

Common Misconception: "Recursion Depth Equals the Number of Moves"

This is worth stating as its own misconception because the two numbers look similar but measure completely different things, and mixing them up leads to wrong predictions about memory use. The recursion depth for n discs is only n — for a 20-disc tower, just 20 stack frames are ever open at once. The move count (and, in this particular program, the total number of function calls across the entire run, since every call prints exactly one move before returning or before making its two children) is 2n − 1 — for 20 discs, over a million. A program can therefore produce an enormous number of moves while using only a small, linear amount of memory for the call stack at any given instant, because most of those million-plus calls happen one after another, not all at once — only the chain of calls that are directly waiting on each other stacks up in memory simultaneously.

Seeing the Recursion Tree

Read the tree in two different ways to see both facts at once. Count the levels from root to leaf — there are three, matching the recursion depth n = 3. Now read the "move" chips from left to right across the whole diagram — move 1 (A→C), move 2 (A→B), move 1 (C→B), move 3 (A→C), move 1 (B→A), move 2 (B→C), move 1 (A→C) — seven chips, matching T(3) = 7, and in exactly the order the program prints them. The tree's height gives you the depth; the tree's total move-chips give you the move count. They are different measurements of the same tree, and confusing them is the misconception addressed above.

Why Recursion, Not Just a Loop?

It is possible to solve Hanoi with pure iteration (a loop and some bit manipulation), but the resulting code has no visible connection to the structure of the problem — you would have to trust a clever trick rather than see why it works. The recursive version is worth learning first precisely because its code is the argument for its own correctness: each line corresponds to a step in the leap-of-faith reasoning we did by hand. This is the general reason recursion earns a place in CBSE's computational-thinking strand alongside iteration — some problems (Hanoi, searching a sorted list by repeatedly halving it, exploring a folder tree on a computer, evaluating a nested arithmetic expression) have a natural recursive structure, where the cleanest, most obviously correct code mirrors that structure directly, and forcing an iterative version onto them trades clarity for a small performance gain that rarely matters at this scale.

Summary

A recursive procedure solves a problem by calling itself on a strictly smaller version of the same problem, stopping at a base case that is answered directly. The Tower of Hanoi's recursive solution moves n-1 discs out of the way, moves the largest disc once, then moves the n-1 discs back on top — the identical sub-procedure used twice, with peg names swapped, not two different pieces of logic. The move count follows the recurrence T(n) = 2T(n-1) + 1, which resolves to the closed form T(n) = 2n − 1 — exponential growth that turns 64 discs into roughly 585 billion years of one-move-per-second work. Separately, the recursion depth — the number of stack frames waiting at once — is only n, a much smaller, linear quantity that should never be confused with the total move count.

Practice: Test Your Understanding

1. Compute T(6) and T(7) using the recurrence T(n) = 2T(n-1) + 1, then check your answers against the closed form 2n − 1.
2. Write out, by hand, the complete sequence of moves for hanoi(2, 'A', 'B', 'C'), and verify the peg contents after every move the way we did for the 3-disc case.
3. If a robot arm can make one disc-move every 0.5 seconds, how long would a 10-disc tower take? How long would a 30-disc tower take? Express the second answer in the most sensible unit (seconds, days, or years).
4. Modify the hanoi function so that instead of printing each move, it counts the total number of moves in a variable and returns that count. Confirm it returns 7 for n = 3 and 15 for n = 4 without printing anything.
5. Explain, in your own words and without looking back at the text, why the two recursive calls inside hanoi can use the exact same code even though one happens before the big disc moves and the other happens after.
6. What is the recursion depth for a 12-disc tower? What is the total move count? State clearly why these two numbers are not the same kind of quantity.