The call stack

What is the call stack?

The call stack is a data structure (a stack—LIFO) that keeps track of active function calls. Every time a function is called, a new stack frame is created and pushed onto the stack. The frame holds:

1. The function’s parameters.
2. Its local variables.
3. The return address (where in the calling code to go when this function finishes).

When the function returns, its frame is popped off the stack, and control goes back to the caller.

How the stack grows and shrinks

Consider this simple example:

function foo() { bar(); }
function bar() { baz(); }
function baz() { return 42; }

foo();

When you call foo():

1. Frame for foo() is pushed.
2. foo() calls bar(), so a frame for bar() is pushed.
3. bar() calls baz(), so a frame for baz() is pushed.
4. baz() returns 42 → its frame is popped.
5. bar() returns → its frame is popped.
6. foo() returns → its frame is popped.

At step 3, the stack contains [foo, bar, baz] (baz on top, the next to run). The stack depth is 3.

Recursion and the call stack

Recursion is just a special case: a function calls itself. Each recursive call pushes a new frame.

Let us trace factorial(4):

1. Call factorial(4) → push frame [n=4].
2. Call factorial(3) → push frame [n=3]. Stack is now [factorial(4), factorial(3)].
3. Call factorial(2) → push frame [n=2]. Stack is now [factorial(4), factorial(3), factorial(2)].
4. Call factorial(1) → push frame [n=1]. Stack is now [factorial(4), factorial(3), factorial(2), factorial(1)].
5. factorial(1) hits base case, returns 1 → pop [n=1]. Stack is now [factorial(4), factorial(3), factorial(2)].
6. factorial(2) gets the answer 1, computes 2 × 1 = 2, returns → pop [n=2]. Stack is now [factorial(4), factorial(3)].
7. factorial(3) gets the answer 2, computes 3 × 2 = 6, returns → pop [n=3]. Stack is now [factorial(4)].
8. factorial(4) gets the answer 6, computes 4 × 6 = 24, returns → pop [n=4]. Stack is empty.

At step 4 (the deepest point), the stack depth is 4. This is n—the size of the input.

The stack has a finite size

Your computer’s memory is limited. The stack (the region of memory where frames live) has a fixed size—typically several megabytes. If recursion goes too deep and keeps pushing frames without popping, it can exhaust this space.

When the stack runs out of memory, a stack overflow occurs: the program crashes with an error like “Maximum call stack size exceeded.” This is a hard limit you cannot ignore.

function badLoop(n) {
  return badLoop(n + 1); // No base case! Infinite recursion.
}

badLoop(0); // Eventually: stack overflow error.

Even with a base case, if the recursion is just deep enough, you will hit the limit:

function deepRecursion(n) {
  if (n === 0) return 1;
  return deepRecursion(n - 1); // Each call pushes a frame.
}

deepRecursion(1000000); // On most systems: stack overflow.

Stack space is the space complexity

From the last lesson, you saw that factorial(n) has O(n) space complexity. Now you understand why: each recursive call pushes a frame. The deepest recursion is n levels, so the stack holds up to n frames at once. That is O(n) stack space.

If you call factorial(1000), 1000 frames accumulate before the deepest call returns. If you call factorial(1000000), the stack overflows long before you finish.

Recursion can be rewritten iteratively

Every recursion can, in principle, be rewritten with an explicit loop and an explicit stack (or other data structure). Recursion is a convenience: the call stack does the bookkeeping for you. But if the stack space is a problem, you can trade recursion for iteration + manual stack management.

Example: compute factorial iteratively (no recursion).

function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

This uses O(1) space—no recursive calls, just a single loop. But it is less intuitive when the problem is naturally recursive (like tree traversal).