Recursion, drawn

A recursive function reads fine line by line, and it can still feel like sleight of hand: the function calls itself, gets back an answer, and somewhere in between a variable held several different values at once without any of them colliding. The doubt is rarely about the logic — the logic is usually short enough to trust on its own. It is about where those in-flight values actually live while a call is waiting on itself. They live in frames, one per call, and a frame is a real thing with a real cost, not a metaphor standing in for something the language quietly handles for free.

One frame per call#

Each call to a function gets its own frame, allocated the moment the call starts and torn down the moment it returns. A frame holds that call’s own parameters and local variables, plus a link back to the call that made it — the frame it hands control to once its own work is done. Python’s own frame objects, documented in the language reference, are built from exactly this shape: a frame carries the local variables it is using, the code it is executing, and a pointer to the frame that called it, one frame per active call, chained together into the stack a debugger walks when it prints a traceback.

That per-call allocation is the whole point of the figure above. Three frames are open at once, and every one of them is labelled n — the same parameter name, because it is the same function running three times. The figure draws a different value into each frame, and that difference is the pattern worth reading: reusing the name does not reuse the storage. A frame’s n disappears the moment that frame returns, and until then it sits untouched by whatever the frame above it is doing with its own n — the two variables happen to share a label and nothing else.

Nothing in that chain unwinds until the frame at the top finishes and hands a value down to the one below it, which is why a recursive function often does its real work on the way back up rather than on the way down. factorial(n) does not know its own answer at the moment it makes the call below it — it is waiting on factorial(n - 1) to return before it can multiply.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)   # waits for the call below before multiplying

The multiplication on that last line cannot run until factorial(n - 1) has returned, so all three frames the figure draws are waiting on the one above them before any can finish. Tree traversal orders makes the same point about a different kind of walk: a depth-first traversal gets its bookkeeping free from the call stack, while a breadth-first one has to keep an explicit queue of its own. The frames above are that free bookkeeping made visible — nothing wrote code to remember that the oldest call is still waiting; the stack remembers it because that is what a call stack does.

Reading the shape of the calls#

A function that calls itself once per invocation, the way factorial does, produces a stack: one frame directly on top of the last, its depth exactly matching however far the recursion went. A function that calls itself twice per invocation produces something else — a tree, with two children branching from every call that has not yet hit its base case. That branching is why a recursion tree is the more useful picture once a function is not simply peeling one layer off at a time: the tree’s shape, not only its depth, is what decides how much work happens.

Naive recursive Fibonacci makes the tree concrete. fib(n) calls fib(n - 1) and fib(n - 2), and each of those calls the same two functions again, so the same smaller subproblems get recomputed on separate branches of the tree instead of being solved once. The tree has roughly two branches per level and about n levels, so its size grows exponentially in n — bounded above by O(2^n) — meaning that raising n by a little raises the work by a lot. That is a complexity class, a property of the tree’s shape, not a measurement of any particular run.

The fix is not a smarter multiplication or a faster interpreter — it is a change to the shape of the calls. Memoising fib so a repeated call returns a cached answer instead of recomputing turns the tree back into something closer to a stack, because every distinct subproblem gets solved once. Rewriting the same logic as a loop that carries the last two values forward removes the tree altogether and does the job with no recursion at all. Both fixes change the shape of the work; neither changes what the function computes.

def fib(n, cache=None):
    if cache is None:
        cache = {}                 # a fresh cache per top-level call
    if n in cache:
        return cache[n]            # subproblem already solved once
    if n <= 1:
        return n
    cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
    return cache[n]

The trees roadmap walks these same shapes from the ground up — what a tree is, how one gets traversed, when balancing pays for itself — but this article is not part of that roadmap; recursion is the mechanism underneath those walks, written up here on its own.

Deep input, not big input#

The failure here is not an infinite recursion — a function that never reaches its base case announces itself almost immediately as a hang or an error, and it is easy to spot and easy to fix once found. What is harder is a function that is genuinely correct, has a real base case, and meets an input deeper than anything it was tested against: a degenerate tree that is really a long chain, a linked structure walked recursively element by element, a parser handed a document nested far past what any test file used.

The tell is the shape of the trigger, not its size. A function that overflows the stack on one input but runs fine on an input with far more total data, just shallower nesting, is not failing because the data is large — it is failing because the data is deep, and depth is exactly what recursion spends one frame per unit of. The error itself gives this away: it names the recursion — a recursion error, a stack overflow — rather than naming anything about the data that produced it, which is why the fix is so often mistaken for a data problem when it is a shape problem.

The obvious fix is not always the right one. Rewriting the recursion as a loop with an explicit stack is not automatically an improvement, even once the depth problem is understood. Many recursive functions read more clearly than the loop that would replace them, and an explicit stack just moves the same values off the call stack and onto a list the code now manages by hand — the memory cost does not disappear, only its visibility does. The judgement worth making is whether the depth is bounded by something under your control: recursion over a fixed, known-shallow structure carries no real risk; recursion over an untrusted or unbounded input is where the ceiling matters.