Recursion and the call stack

What this chapter covers

Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. It's not a data structure — it's a technique — but it runs on one you already built: the call stack from the stacks chapter. Every call pushes a frame; every return pops one. So recursion is really a stack you don't have to manage by hand, and understanding that is the difference between recursion feeling like magic and feeling like machinery. This chapter makes it concrete with the Towers of Hanoi, whose recursive solution is three lines and whose cost is exponential, and it sets up the divide-and-conquer sorts that fill the rest of the tier.

A bit of history

The Towers of Hanoi was invented in 1883 by the French mathematician Édouard Lucas, who sold it as a toy wrapped in a legend: in a temple, monks move 64 golden disks between three posts, and when they finish, the world ends. They're safe for a while — we'll see why. Recursion as a programming idea is nearly as old as programming: John McCarthy built it into LISP in 1958, making a function calling itself a first-class thing rather than a trick, and the mathematical theory of recursive functions (Kleene, Church, and others in the 1930s) predates the computers that run it. The call stack that makes recursion work in hardware — a frame pushed per call — was standardized in the same 1950s era that gave us the stack itself. So the puzzle, the technique, and the machinery all come together here.

The intuition

A recursive solution has two parts, and both are mandatory. The base case is the smallest version of the problem you can answer outright — the place the recursion stops. The recursive case solves a bigger problem by reducing it to one or more smaller problems of the same kind and combining their answers. If either is missing — no base case, or a recursive case that doesn't shrink the problem — the recursion never stops, and you crash.

Towers of Hanoi is the perfect illustration because the recursive insight is the whole solution. To move n disks from peg A to peg C: move the top n−1 disks out of the way onto peg B (a smaller Hanoi problem), move the single largest disk from A to C, then move those n−1 disks from B onto C (another smaller Hanoi problem). You never say how to move n−1 disks — you trust the recursion to do it, the same way you're trusting it to move n. That leap of faith, "assume it works for smaller, use that to solve bigger," is how you think recursively.

Complexity: how it scales

A recursion's cost comes from its recurrence — a formula for the work at size n in terms of smaller sizes. Hanoi does two subproblems of size n−1 plus one move:

That's exponential. Four disks take 15 moves, ten take 1023, twenty take over a million, and Lucas's 64 golden disks take $2^{64}-1$ moves — about 585 billion years at one move a second, so the monks aren't a threat. The chart makes the shape unmistakable — the move count doubles with every disk added:

Space is a separate cost, and it's the one recursion adds on top of any algorithm: each pending call holds a frame on the call stack, so recursion of depth d uses $O(d)$ stack space even when an iterative version would use O(1). For Hanoi the depth is only n, but for a recursion that goes n deep on a large n, that stack space — and Python's limit on it — becomes the constraint.

What it's good at, what it isn't

Recursion is the right tool when a problem is naturally self-similar — when a big instance genuinely decomposes into smaller instances of the same shape. Trees, divide-and-conquer sorts, backtracking searches, and anything defined by a recurrence come out shorter and clearer as recursion than as a hand-managed loop, because the call stack does the bookkeeping you'd otherwise write yourself. When the structure fits, recursive code often reads like the definition of the problem.

Where it costs you is calls and depth. Every recursive call has overhead — a frame pushed and popped — that a loop avoids, and every language caps how deep the stack can go. When a recursion has a trivial iterative twin (factorial, summing a list), the loop is usually the better choice. And a recursion that can go very deep on real input will overflow the stack; then you either rewrite it as a loop or make the stack explicit, trading the language's stack for one you control.

The data, or the inputs

The animation solves a four-disk Hanoi — 15 moves, small enough to watch every one. The face-off computes factorials at increasing n to measure what the recursion itself costs against its iterative twin and against math.factorial. And the growth chart is pure arithmetic: the exact move count $2^n - 1$, which needs no benchmark because it's exact.

Build it, one function at a time

Here's the whole Hanoi solver — the three-line recursion that reads like the strategy: move n−1 aside, move the big disk, move n−1 back:

def hanoi(n, source, target, auxiliary, moves=None):
    """Move n disks from `source` to `target` using `auxiliary`, one disk at a
    time, never placing a larger disk on a smaller one.

    The recursion IS the strategy: to move n disks, first move the top n-1 out of
    the way onto the spare peg, move the single largest disk across, then move the
    n-1 back on top of it. Each of those "move n-1" steps is the same problem, one
    size smaller — so the function calls itself twice."""
    if n == 0:
        return
    hanoi(n - 1, source, auxiliary, target, moves)   # n-1 disks off to the spare peg
    if moves is not None:
        moves.append((n, source, target))            # move the big disk across
    hanoi(n - 1, auxiliary, target, source, moves)   # n-1 disks back on top

Factorial is the smallest complete recursion — a base case and one self-call:

def factorial(n):
    """The textbook recursion: n! = n * (n-1)!, bottoming out at 0! = 1. The base
    case is what stops the recursion — forget it and you recurse forever."""
    if n <= 1:
        return 1
    return n * factorial(n - 1)

And here's the transformation that demystifies recursion: summing a nested list with the call stack, then the identical result with an explicit stack. The second is what the first was doing all along — proof that recursion is just a stack in disguise, and your escape hatch when the depth limit looms:

def sum_nested(node):
    """Recursively sum a nested list (a tree of numbers). The call stack quietly
    remembers where you were in each level."""
    total = 0
    for child in node:
        total += sum_nested(child) if isinstance(child, list) else child
    return total


def sum_nested_iter(root):
    """The same sum with an EXPLICIT stack instead of recursion. This is exactly
    what the call stack was doing under the recursive version — made visible.
    Any recursion can be rewritten this way; sometimes you must, to dodge Python's
    recursion-depth limit."""
    stack = [root]
    total = 0
    while stack:
        node = stack.pop()
        if isinstance(node, list):
            stack.extend(node)
        else:
            total += node
    return total

Watch it work

Here's the four-disk Hanoi solving itself, one move per frame. All four disks start stacked on peg A, largest at the bottom. Step through it and watch the pattern the recursion produces: to get the big bottom disk from A to C, everything above it first has to migrate to B, then come back. Fifteen moves, and not one of them puts a larger disk on a smaller one — the recursion guarantees it. Notice the self-similarity: the first seven moves are a complete three-disk solve moving the top three to B, and the last seven are another moving them back:

The complete code

Both versions in one place — flip between them. The from-scratch tab has the recursions: Hanoi, factorial, and the explicit-stack rewrite. The library tab is math.factorial, the iterative C version you'd actually call — a reminder that the standard library often unrolls recursion into a loop for exactly the reasons this chapter gives.

"""Recursion — a function that solves a problem by calling itself on a smaller
piece of the same problem.

This isn't a data structure; it's a technique, and it runs on one you already
know. Every recursive call pushes a frame onto the call stack from chapter four;
returning pops it. So recursion is really just a stack you don't have to manage
by hand. This chapter makes that concrete with the Towers of Hanoi — a puzzle
whose recursive solution is three lines and whose cost is exponential.
"""


# region: hanoi
def hanoi(n, source, target, auxiliary, moves=None):
    """Move n disks from `source` to `target` using `auxiliary`, one disk at a
    time, never placing a larger disk on a smaller one.

    The recursion IS the strategy: to move n disks, first move the top n-1 out of
    the way onto the spare peg, move the single largest disk across, then move the
    n-1 back on top of it. Each of those "move n-1" steps is the same problem, one
    size smaller — so the function calls itself twice."""
    if n == 0:
        return
    hanoi(n - 1, source, auxiliary, target, moves)   # n-1 disks off to the spare peg
    if moves is not None:
        moves.append((n, source, target))            # move the big disk across
    hanoi(n - 1, auxiliary, target, source, moves)   # n-1 disks back on top
# endregion


# region: factorial
def factorial(n):
    """The textbook recursion: n! = n * (n-1)!, bottoming out at 0! = 1. The base
    case is what stops the recursion — forget it and you recurse forever."""
    if n <= 1:
        return 1
    return n * factorial(n - 1)
# endregion


# region: factorial_iter
def factorial_iter(n):
    """The same answer with a loop instead of recursion. Every recursion has an
    iterative twin; when the twin is this simple, prefer it — no call overhead,
    no depth limit."""
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result
# endregion


# region: explicit_stack
def sum_nested(node):
    """Recursively sum a nested list (a tree of numbers). The call stack quietly
    remembers where you were in each level."""
    total = 0
    for child in node:
        total += sum_nested(child) if isinstance(child, list) else child
    return total


def sum_nested_iter(root):
    """The same sum with an EXPLICIT stack instead of recursion. This is exactly
    what the call stack was doing under the recursive version — made visible.
    Any recursion can be rewritten this way; sometimes you must, to dodge Python's
    recursion-depth limit."""
    stack = [root]
    total = 0
    while stack:
        node = stack.pop()
        if isinstance(node, list):
            stack.extend(node)
        else:
            total += node
    return total
# endregion

"""Recursion is a technique, not a data structure, so there's no single library to
race against. The honest counterpart is twofold: for problems with an iterative
twin, the loop version is the "reference" (and usually what the standard library
ships — `math.factorial` is iterative C, not recursive); and for the general case,
an explicit stack is the mechanical way to remove recursion.

So the face-off compares our recursive code against its iterative equivalent and
against `math.factorial`, to measure what the recursion itself costs.
"""
import math


# region: math_factorial
def factorial_lib(n):
    """math.factorial: the standard library's version — iterative, in C, and the
    one you'd actually call. No recursion, so no depth limit and no call overhead."""
    return math.factorial(n)
# endregion

Scratch vs library

For a problem with an iterative twin, recursion is a small tax. Computing factorial at n = 800, our recursive version took about 0.12 ms, the iterative twin 0.08 ms (the recursion's call overhead, roughly 1.4 times slower), and math.factorial 0.01 ms — the C implementation an order of magnitude beyond both. The lesson isn't that recursion is slow; it's that when a clean loop exists, it wins on both speed and the depth limit, so recursion should earn its place by making the code genuinely clearer or by fitting a problem no loop expresses well. Hanoi is that kind of problem — try writing its solver as a loop and you'll end up simulating a stack, which is the recursion you were avoiding.

Where you'll actually meet it

Recursion is the natural language for anything tree-shaped, which is most of the rest of this book. Every tree traversal is a recursion. The divide-and-conquer sorts — merge sort and quicksort, next — are recursions that split, solve, and combine. Backtracking searches (N-Queens, later) recurse down a decision and undo on the way back up. Parsers recurse through nested grammar; file-system walks recurse through directories; the graph searches recurse (or use the explicit stack this chapter showed) through neighbors. Wherever a problem contains smaller copies of itself, recursion is how you write it down.

Takeaways

Recursion solves a problem by reducing it to smaller instances of itself, stopping at a base case, and it runs on the call stack — each call a frame, so depth costs O(d) space and is bounded by the language. Its cost is whatever its recurrence says, which for Hanoi is an exponential $2^n - 1$. When an iterative twin exists it's usually the better choice, but for genuinely self-similar problems recursion is shorter, clearer, and closer to the definition than any loop.

The technique earns its keep starting now. The next three chapters are sorts, and the best of them — merge sort and quicksort — are recursion at its most useful: split the array, sort the halves by recursing, combine. Keep the Hanoi picture in mind: solve the smaller problem by trusting the recursion, and the whole thing falls out.