How Recursion Works: The Call Stack Explained

The call stack is the data structure that makes recursion possible. Every time a function is called, the computer pushes a stack frame holding that call’s parameters, local variables, and where to resume when it returns. A recursive function simply stacks many frames of itself; as each base case returns, the frames pop off one by one and their results combine. Understanding this is the difference between recursion feeling magical and feeling mechanical.

What is a stack frame?

When you call a function, the runtime allocates a frame (also called an activation record) on the call stack. The frame stores:

• the arguments passed in,
• the function’s local variables,
• the return address — the spot to continue once this call finishes.

When the function returns, its frame is popped and control jumps back to the caller. A stack is LIFO (last in, first out), so the most recent call always finishes first — exactly the order recursion needs.

Watching the stack grow and shrink

Take factorial(3). Each call pushes a frame and pauses, waiting for the smaller call to return a value before it can multiply:

long long factorial(int n) {
    if (n <= 1) return 1;            // base case returns up the stack
    long long smaller = factorial(n - 1); // frame pauses here, waiting
    return n * smaller;              // resume once the inner call returns
}

long factorial(int n) {
    if (n <= 1) return 1;            // base case returns up the stack
    long smaller = factorial(n - 1); // frame pauses here, waiting
    return n * smaller;              // resume once the inner call returns
}

function factorial(n) {
  if (n <= 1) return 1;             // base case returns up the stack
  const smaller = factorial(n - 1); // frame pauses here, waiting
  return n * smaller;              // resume once the inner call returns
}

def factorial(n):
    if n <= 1:
        return 1                 # base case returns up the stack
    smaller = factorial(n - 1)   # frame pauses here, waiting
    return n * smaller           # resume once the inner call returns

The stack over time (each line is a frame, newest on top):

push factorial(3)            factorial(3)
push factorial(2)            factorial(2)  factorial(3)
push factorial(1)            factorial(1)  factorial(2)  factorial(3)
factorial(1) returns 1  ->   pops, hands 1 to factorial(2)
factorial(2) returns 2  ->   pops, hands 2 to factorial(3)
factorial(3) returns 6  ->   pops, final answer 6

Two phases happen: a winding phase going down (frames push as the problem shrinks) and an unwinding phase coming back up (frames pop as results return and combine). Work you put before the recursive call runs on the way down; work after it runs on the way up.

For beginners: This is why printing before vs after the recursive call gives different orders. Before = top-down; after = bottom-up. The same idea powers pre-order vs post-order tree traversals.

How the base case “returns up the stack”

The base case is where a concrete value first appears. That value is handed to the frame directly below, which finishes its own computation and returns its result further down — like a relay passing a baton. Nothing returns until the deepest call hits the base case, so a missing or unreachable base case means frames pile up forever.

Stack overflow: when recursion runs out of room

The call stack has a finite size. Push too many frames — deep or infinite recursion — and you get a stack overflow crash. This snippet recurses too deep on purpose:

int deep(int n) {
    if (n == 0) return 0;
    return 1 + deep(n - 1); // ~100000+ frames may overflow the stack
}
// deep(1000000); // likely crashes

int deep(int n) {
    if (n == 0) return 0;
    return 1 + deep(n - 1); // throws StackOverflowError when too deep
}
// deep(1_000_000); // likely crashes

function deep(n) {
  if (n === 0) return 0;
  return 1 + deep(n - 1); // RangeError: Maximum call stack size exceeded
}
// deep(1000000); // likely crashes

def deep(n):
    if n == 0:
        return 0
    return 1 + deep(n - 1)  # RecursionError past sys.getrecursionlimit()

# deep(1000000)  # likely crashes (Python default limit ~1000)

Going deeper: Some languages optimize tail calls (where the recursive call is the very last action) into loops, using O(1) stack space — but C++, Java, JavaScript, and Python generally do not guarantee this, so don’t rely on it. For very deep problems, convert to iteration with an explicit stack. Python even caps recursion depth (~1000) by default.

The space cost of recursion

Because every paused call keeps a frame alive, a recursion that nests d levels deep uses O(d) stack space even if it allocates nothing else. For factorial(n) that’s O(n); for a balanced tree traversal it’s O(height). Always count the stack when analyzing recursive complexity.

Next: get the two pieces right every time in base & recursive cases.