Recursion & the Call Stack

Recursion is one of those ideas that sounds circular — and it is, deliberately. A recursive function solves a problem by solving a smaller version of the same problem. The trick is knowing when to stop.

The two required ingredients

Every recursive function must have exactly these two parts:

1. Base case — the input is small enough to answer directly, with no further calls.
2. Recursive case — reduce the input toward the base case and call yourself.

If you are missing the base case, the function will call itself forever (until the runtime kills it). If the recursive case never moves toward the base, same result.

Here is the simplest example: factorial.

def factorial(n):
    if n <= 1:          # base case
        return 1
    return n * factorial(n - 1)   # recursive case: n shrinks by 1 each time

factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1). At n = 1 the base case fires and the function returns. The returns then propagate back up: 1 → 2 → 6 → 24.

What actually happens in memory

Every function call allocates a stack frame on the call stack — a small block of memory that holds the function’s local variables, the argument values, and the return address (where to continue after the call finishes). When the function returns, its frame is popped off.

Recursion means pushing many frames before popping any of them. For factorial(4) you get four frames deep before the first return.

Step through the visualization above. Watch the call stack grow one frame per call, and then shrink one frame per return as the result bubbles back up. The return value of each frame feeds directly into the calculation in the frame below it.

Recursion vs. iteration

Anything you can do with recursion you can also do with an explicit loop (and a stack if needed). The choice is about clarity and trade-offs:

For a simple factorial or list sum, iteration is usually safer. Recursion shines on problems that are themselves defined recursively — like traversing a tree or computing the Fibonacci sequence.

Try it yourself

This playground has two recursive functions. Run them, then try modifying the inputs.

Notice that list_sum slices off the first element each call — the list shrinks by one every time, guaranteeing it reaches the empty-list base case.

The stack overflow problem

Languages like Haskell and Scala support tail-call optimization — when the recursive call is the very last operation in the function, the compiler reuses the current frame instead of pushing a new one. Python does not do this, so even tail-recursive Python code allocates a new frame every call.

Naive fibonacci is exponential

Here is where recursion gets genuinely interesting. The Fibonacci sequence is defined recursively:

fib(n) = fib(n-1) + fib(n-2)   for n > 1
fib(0) = 0,  fib(1) = 1

Translating that definition directly to code:

def fib(n):
    if n <= 1:          # base case
        return n
    return fib(n - 1) + fib(n - 2)   # two recursive calls

This looks clean but hides an exponential cost. To compute fib(5) you compute fib(4) and fib(3). But fib(4) also needs fib(3). So fib(3) is computed twice. fib(2) is computed three times. The total number of calls grows as O(2ⁿ).

To see this concretely: sketch fib(5) as a tree. Each node fans into two children. The left branch for fib(4) spawns its own fib(3), which duplicates the fib(3) already needed at the top level — pure wasted work.

The fix is memoization: cache each result the first time you compute it and return the cached value on subsequent calls. That reduces fib from O(2ⁿ) to O(n). Python ships a one-liner for this:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Memoization is the gateway to dynamic programming — storing intermediate results to avoid redundant work. If you want to dig deeper, that is the next stop.

Quick check