Recursive Functions and the Call Stack in JavaScript

Recursive Functions and the Call Stack in JavaScript

A recursive function is one that calls itself. Each call creates a new frame on the call stack. Recursion is powerful but must be bounded.

How Recursion Uses the Stack

function factorial(n) {
  if (n <= 1) return 1;     // base case
  return n * factorial(n - 1);
}
factorial(3);

Stack as it grows: [GEC, factorial(3), factorial(2), factorial(1)].

Stack as it unwinds:

• factorial(1) returns 1, frame popped.
• factorial(2) returns 2 * 1 = 2, frame popped.
• factorial(3) returns 3 * 2 = 6, frame popped.
• Result: 6.

Each frame has its own n. The multiplication happens on the way back up.

The Base Case Is Essential

Without a base case, the function calls itself forever and the stack overflows:

function bad() { return bad(); }
bad(); // RangeError: Maximum call stack size exceeded

Every recursive function needs a condition that stops the recursion.

Recursion vs Iteration

Anything recursive can be written iteratively. Iteration uses constant stack space; recursion uses one frame per call.

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

For deep inputs, prefer iteration. For naturally recursive problems (trees, graphs, divide-and-conquer), recursion reads better.

Tail Call Optimization

A tail call is a call where the result is returned directly (no further work after the call). ES6 spec includes tail call optimization, but V8 and most engines do not implement it. So deep recursion still overflows.

Trampolines

For deep recursion without TCO, use a trampoline: wrap recursive returns in thunks and run them in a loop.

function trampoline(fn) {
  return function (...args) {
    let result = fn(...args);
    while (typeof result === "function") result = result();
    return result;
  };
}

Common Use Cases

• Tree traversal (DOM, JSON, AST).
• Divide-and-conquer (merge sort, quicksort).
• Backtracking (permutations, puzzles).
• Graph traversal (DFS).

The Takeaway

Recursion pushes a frame per call and unwinds on return. Every recursive function needs a base case. JS engines do not optimize tail calls, so deep recursion overflows the stack; convert to iteration or use a trampoline for those cases.