Recursion

Two parts, and both are required

A recursion is a base case and a step that moves towards it. Miss the base case and it never stops; write a step that does not shrink the problem and it never stops either — and both look the same from outside: RangeError: Maximum call stack size exceeded.

The discipline that makes it work is to trust the recursive call. Assume factorial(n - 1) is already correct and write only the one step. Trying to trace the whole thing in your head is what makes recursion feel hard.

function factorial(n) {
  if (n <= 1) return 1;            // base case: the version you can answer
  return n * factorial(n - 1);     // recursive case: a SMALLER version
}

The stack is real memory

Every pending call holds a frame: its arguments, its locals, and where to return to. A recursion of depth n uses O(n) memory even when it does no allocation at all, and the stack is small — a few tens of thousands of frames in a browser, then it throws.

So depth matters. Recursion over a balanced tree is depth O(log n) and perfectly safe; recursion over a linked list of a million nodes is depth 1 000 000 and will not survive.

text

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1) → 1
    ← 2
  ← 6
← 24                       four frames alive at the deepest point

Tail calls, and why you cannot rely on them

A language with tail-call elimination turns the second form into a loop and uses O(1) stack. The specification for JavaScript requires it; almost no engine implements it, so in practice the second form still overflows. Python never had it and Guido has said it never will.

Treat the accumulator form as good style and not as a guarantee. When depth is the problem, convert to a loop properly.

/* not a tail call: the multiply happens AFTER the call returns */
return n * factorial(n - 1);

/* a tail call: nothing is left to do, so the frame could be reused */
function factorial(n, acc = 1) {
  if (n <= 1) return acc;
  return factorial(n - 1, n * acc);
}

Converting to a loop

That is the mechanical recipe, and it always works: whatever the call stack was holding, hold it yourself in an array. The heap is far bigger than the stack, so the iterative version handles depths the recursive one cannot.

linear recursion → a plain loop

let acc = 1;
for (let i = n; i > 1; i--) acc *= i;
return acc;

branching recursion → a loop with an explicit stack

function sumTree(root) {
  let total = 0;
  const stack = [root];                     // the frames, made visible

  while (stack.length) {
    const node = stack.pop();
    if (!node) continue;
    total += node.value;
    stack.push(node.left, node.right);
  }

  return total;
}

When recursion is the wrong tool

And where it is right, it is very right: merge sort, quicksort, tree traversal, flood fill, parsing and backtracking are all shorter, clearer and less bug-prone written recursively.

When the same subproblem is solved twice. Naive Fibonacci makes 2.7 million calls for fib(32) and is exponential. Memoise it and it is linear — that is the dynamic-programming lesson.
When the depth is the size of the input. A list, a file, a long chain: use a loop.
When a loop is simply clearer. Recursion earns its place on shapes — trees, nested structures, divide and conquer — and rarely on sequences.

Two parts, and both are required

The stack is real memory

Tail calls, and why you cannot rely on them

Converting to a loop

When recursion is the wrong tool

Practice