Recursion and Stacks

The Recursive Call Stack

When a function calls itself, the programming language pushes a new stack frame onto the call stack. Each frame stores the function's parameters, local variables, and the return address (where to go back after the function finishes).

The call stack grows downward as you recurse deeper and shrinks upward as functions return. This is exactly how a stack data structure works: last in, first out.

Consider a simple function that counts down from n to zero. Each call to countdown(n-1) adds a new frame. When n reaches zero, the base case stops recursion and each frame pops off in reverse order.

Factorial Walkthrough

Let us trace factorial(4) step by step to see the stack grow and shrink.

factorial(4):
  push frame: n=4, waiting for factorial(3)
    push frame: n=3, waiting for factorial(2)
      push frame: n=2, waiting for factorial(1)
        push frame: n=1, waiting for factorial(0)
          base case: return 1
        pop n=1: return 1 * 1 = 1
      pop n=2: return 2 * 1 = 2
    pop n=3: return 3 * 2 = 6
  pop n=4: return 4 * 6 = 24
Result: 24

The stack reached a depth of 4 frames. For factorial(1000), it would reach 1000 frames. Each frame takes memory, which is why very deep recursion can be problematic.

Fibonacci and Stack Depth

The naive recursive Fibonacci function is a classic example of how recursion can explode in stack usage. To compute fib(5), it makes two recursive calls per level, creating a tree of calls:

fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1) -> 1
        fib(0) -> 0
      fib(1) -> 1
    fib(2)
      fib(1) -> 1
      fib(0) -> 0
  fib(3)
    fib(2)
      fib(1) -> 1
      fib(0) -> 0
    fib(1) -> 1

The maximum stack depth is proportional to n, but the total number of calls grows exponentially. For fib(40), there are over a billion calls. This makes naive recursive Fibonacci both slow and memory-hungry.

Recursion vs Iteration

Converting Recursion to an Explicit Stack

You can replace any recursion with an explicit stack data structure. This gives you control over memory and eliminates stack overflow risk. The pattern is: instead of making a recursive call, push the state onto a stack and loop.

def factorial_iterative(n):
    stack = []
    stack.append(n)
    result = 1
    while stack:
        val = stack.pop()
        if val > 0:
            result *= val
            stack.append(val - 1)
    return result

This approach uses heap memory (the explicit stack) instead of call stack memory. You can grow it to millions of elements without crashing.

Tail Recursion and Optimization

Tail recursion happens when the recursive call is the absolute last operation in the function. No computation happens after the recursive call returns.

// Tail-recursive factorial
function factorial(n, acc = 1) {
    if (n === 0) return acc;
    return factorial(n - 1, n * acc);  // tail call
}

Some compilers and interpreters optimize tail calls by reusing the current stack frame (Tail Call Optimization or TCO). This effectively turns recursion into iteration under the hood. Languages like Scheme, Scala, and Kotlin support TCO. JavaScript engines support it in strict mode for some cases. Python does not support TCO.

Stack Overflow from Deep Recursion

Every language has a maximum call stack depth. In JavaScript it is typically around 10,000 to 25,000 frames. In Python it defaults to 1000. In C/C++ it depends on stack size (usually 1-8 MB).

When you exceed this limit, the program crashes with a stack overflow error. Common causes include:

• Recursing on very large inputs (e.g., factorial of 100,000)
• Missing or incorrect base case (infinite recursion)
• Recursive traversal of very deep trees or linked lists

The fix is either to convert to iteration, increase the stack size (not recommended for production), or use tail call optimization where available.

When to Use Recursion vs Stack Iteration

Use recursion when the problem is naturally recursive (trees, graphs, divide-and-conquer), the input depth is bounded and small, and readability matters more than raw performance.

Use an explicit stack iteration when input size can be very large, memory is constrained, stack overflow is a real risk, or you need precise control over the traversal order.

A practical rule: if your recursion depth can exceed a few thousand frames, switch to an explicit stack.