Recursion vs Iteration: How the Call Stack Makes Recursion Work

#webdev #tutorial

Recursion and iteration solve the same fundamental problem — do something repeatedly — but they manage the "where was I?" bookkeeping in completely different places. Iteration keeps it in variables you can see. Recursion hands it to the call stack, which is exactly why recursion feels like magic and occasionally blows up in your face.

Two ways to repeat work

Iteration repeats with an explicit loop. You declare the state up front — a counter, an accumulator — and update it on each pass. Nothing is hidden; the entire "memory" of the loop lives in variables sitting in the current function.

Recursion repeats by having a function call itself with a smaller version of the problem. There is no visible counter. Instead, each call says "I'll solve this once I know the answer to the slightly smaller case," and waits. The waiting is the key idea, and it is what the call stack manages.

Here is factorial both ways.

# Iterative: state is explicit
def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Recursive: state lives on the call stack
def factorial_rec(n):
    if n <= 1:          # base case
        return 1
    return n * factorial_rec(n - 1)

The iterative version walks i from 2 to n, multiplying as it goes. The recursive version peels off one n at a time and defers the multiplication until the smaller call returns.

What the call stack actually does

Every time a function is called, the runtime pushes a new stack frame. That frame holds the call's local variables (here, the value of n for this particular call) and a return address — the spot in the calling code to jump back to once this call finishes.

So factorial_rec(4) pushes a frame, then calls factorial_rec(3), which pushes another frame, down to factorial_rec(1). At that point four frames are stacked, each frozen mid-multiplication, each remembering its own n. The base case (n <= 1) is what stops the descent — without it, the function would keep calling itself forever.

Once the base case returns 1, the stack unwinds: the n=2 frame resumes, computes 2 * 1, returns; the n=3 frame computes 3 * 2; and so on back up. Each frame finishes the work it had paused, using the value the frame below it just produced.

That is the whole mechanism. Recursion does not have special looping powers — it just uses the call stack as an automatic, invisible stack of "things I still need to finish."

When recursion breaks, and tail calls

The call stack is finite. Push too many frames and you get a stack overflow — the runtime runs out of stack space and crashes (in Python, a RecursionError; in many languages, a hard segfault-style failure). Two common causes: a missing or wrong base case, so the recursion never stops, and a base case that is correct but reached only after far too many frames, like recursing over a million-element list.

Some languages mitigate this with tail-call optimization (TCO). If a recursive call is the very last thing a function does — its result is returned directly, with no pending work like a multiply waiting on it — the runtime can reuse the current frame instead of pushing a new one, turning the recursion into a loop under the hood. Scheme and other functional languages guarantee this; many mainstream languages, including Python and most JavaScript engines, do not perform it, so a "tail-recursive" function there still grows the stack frame by frame.

Recursion and iteration are equally powerful — anything you can write recursively can be rewritten as a loop, sometimes by using an explicit stack or queue data structure to hold the state the call stack was managing for you. For deep or unbounded recursion in a language without tail-call optimization, this is not just a style choice; converting to an explicit loop is often the only way to avoid a stack overflow.

So which should you reach for? Recursion shines when the problem is naturally self-similar — tree traversals, parsers, divide-and-conquer algorithms — where a loop would force you to manage a stack by hand anyway. Iteration wins for flat, linear repetition and for hot paths where avoiding call overhead matters. The factorial above is honestly a better fit for a loop; it is just the clearest possible teaching example.