Recursion and the Call Stack

Recursion is what you do when a problem contains a smaller copy of itself. To price an option on a binomial tree you need the value at the node above, which needs the values at the two nodes above that, and so on until you hit expiry where the answer is obvious. To sum a directory tree you sum each subdirectory. Rather than write the loop that manages all of that, you write a function that handles one level and calls itself for the rest.

Every recursive function needs exactly two pieces. A base case: a version of the problem small enough to answer outright, with no further calls. And a recursive case: a rule that reduces the problem and calls itself on the smaller version. Miss the base case and the function never stops. Fail to actually shrink the problem and it also never stops. Those two failures cause almost every recursion bug you will ever see.

The call stack is the state you did not write

When a function calls another function, the machine has to remember where to come back to. It pushes a stack frame holding the return address, the arguments, and the local variables. When the call finishes, that frame is popped and execution resumes where it left off. Recursion is just this ordinary mechanism applied to a function calling itself, so you end up with many frames of the same function alive at once, each holding its own copy of the arguments.

This is why recursion costs memory. A recursion of depth $d$ holds $d$ frames, so the space cost is

$$O(d)$$

on top of whatever the algorithm allocates. For a balanced tree $d \approx \log n$ and that is nothing. For a linked list walked recursively $d = n$, and at a few tens of thousands of frames the process runs out of stack and crashes.

Worked example: trace fact(4)

def fact(n):            # time O(n), stack space O(n)
    if n <= 1:          # base case
        return 1
    return n * fact(n - 1)

Follow it line by line. fact(4) cannot return yet, it needs fact(3), so it parks with n = 4 and pushes. Same for fact(3) and fact(2). Then fact(1) hits the base case and returns 1 outright. Now the stack unwinds: fact(2) computes 2 × 1 = 2, fact(3) computes 3 × 2 = 6, fact(4) computes 4 × 6 = 24. Four calls, four frames, one multiplication each, so $O(n)$ time and $O(n)$ stack.

Notice that the multiplication in each frame happens after the recursive call returns. That is why the frame has to stay alive, and it is the difference between recursion that costs stack and a loop that does not.

Worked example: why naive Fibonacci is a disaster

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Trace fib(5). It calls fib(4) and fib(3). But fib(4) also calls fib(3), which recomputes the same subtree from scratch. fib(2) is evaluated five separate times. The call tree roughly doubles at each level, so the cost is about $O(2^n)$: fib(40) is already a billion calls, while the stack depth stays a harmless $n$.

The fix is to remember answers you have already computed:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):             # time O(n), each n computed once
    return n if n < 2 else fib(n - 1) + fib(n - 2)

That single decorator takes it from exponential to linear, because each distinct n is now evaluated once and reused. Recursion plus a cache is top-down Dynamic Programming Basics — the recursion expresses the rule, the cache kills the repeated work.

Where it shows up

In interviews, recursion is the backbone of tree traversals, backtracking (n-queens, subsets, sudoku), divide-and-conquer sorts, and every memoisation question. Expect to be asked for the time and the stack-space cost, and to convert a recursive solution to an iterative one under follow-up pressure.

On a desk the same shape recurs: Binomial Option Pricing rolls back through a tree, American-option early-exercise checks compare a node's continuation value to its exercise value, risk aggregation walks a book grouped by strategy then trader then desk, and dependency resolution in a backtest engine is a recursive graph walk. Production code usually keeps the recursive formulation for clarity at shallow depth and switches to an explicit stack once the depth is data-dependent.