Recursion and the call stack

Recursion isn't magic — it's the ordinary function call stack, used deliberately. Seeing the stack frames makes both "why does this work" and "why did this crash" obvious.

Intermediate

4 min read

What a function call actually does to the stack

Every function call pushes a new stack frame onto the call stack — a chunk of memory holding that call's local variables, its parameters, and the address to return to when it finishes. The function returns by popping its frame off and resuming execution wherever the caller left off. This is true of every function call, recursive or not — recursion is just the case where a function's own body calls itself, so its frames stack up on top of each other before any of them return:

def countdown(n):
    if n == 0:
        print("liftoff")
        return
    print(n)
    countdown(n - 1)
 
countdown(3)

3            <- countdown(3)'s frame is active
2            <- countdown(2)'s frame pushed on top of countdown(3)'s
1            <- countdown(1)'s frame pushed on top of that
liftoff      <- countdown(0)'s frame; hits the base case, returns

Four separate frames existed simultaneously at the deepest point — countdown(0) running while countdown(1), countdown(2), and countdown(3) were all still paused, each waiting at the line right after its own recursive call, each with its own independent copy of n.

The two things every correct recursive function needs

def factorial(n):
    if n == 0:            # base case — stops the recursion
        return 1
    return n * factorial(n - 1)   # recursive case — must move toward the base case

A base case that doesn't recurse, and a recursive case that's guaranteed to move closer to the base case on every call (here, n - 1 strictly decreases toward 0). Miss the base case, or write a recursive case that doesn't actually converge, and the function calls itself forever — or rather, until it runs out of stack space.

What a stack overflow actually is

def broken(n):
    return broken(n)   # no base case at all — never terminates
 
broken(1)   # RecursionError: maximum recursion depth exceeded

Each unreturned call keeps its frame on the stack, and the stack is a fixed-size region of memory. Enough simultaneously-open frames exhaust it — that's a stack overflow, and it's the concrete, physical reason "no base case" isn't just a logic bug but a crash. Python additionally enforces a configurable recursion depth limit (sys.getrecursionlimit(), default 1000) specifically to turn what would otherwise be a memory-corrupting crash into a catchable RecursionError well before the real stack limit is reached.

Why recursion fits some problems more naturally than a loop

Problems with a naturally recursive structure — traversing a tree, where each node's subtree is itself a smaller tree of the same shape — map directly onto recursion, since "solve the same problem on a smaller version of the input" is the tree's actual structure:

def tree_sum(node):
    if node is None:
        return 0
    return node.value + tree_sum(node.left) + tree_sum(node.right)

Writing this iteratively requires manually managing an explicit stack or queue to track "which subtrees are left to visit" — which is exactly what the call stack was already doing for you, automatically, in the recursive version. This is the real reason recursion is chosen over a loop here: not because it's shorter, but because the call stack is the correct data structure for the problem's own shape, and reimplementing it by hand adds code without adding clarity.

The real cost: when recursion is the wrong choice

Deep recursion (proportional to input size, not tree depth) risks hitting the recursion limit on large inputs — summing a Python list recursively, one element per call, fails around n=1000 where a simple loop wouldn't. And unlike some languages, Python does not perform tail-call optimization, so even a recursive call written in "tail position" still keeps its full stack frame around. For anything where the recursion depth scales with a potentially large, unbounded input (as opposed to something naturally shallow like a balanced tree's height), an explicit loop or an explicit stack is the safer choice.