Recursion

Recursion is a programming technique where a function calls itself to solve a smaller instance of the same problem. While loops like for and while rely on mutable state to track progress, recursion relies on the function call stack. This functional approach is especially powerful when traversing hierarchical data structures, like the DOM tree or complex nested JSON objects, where the depth of the nesting is unknown ahead of time.

A recursive function must have a condition to stop calling itself. Otherwise, the function will call itself indefinitely.

Without a stopping condition, recursion is no different from an infinite loop. However, instead of just freezing the browser, an infinite recursion will violently crash the engine as it runs out of memory allocated for the call stack. Let’s look at a simple countdown, mapping out how the stack frames grow:

Notice how we have a condition to halt the recursion:

function countdown(n) {
  console.log(n);
  if (n <= 0) return;
  countdown(n - 1);
}
countdown(2);

2
1
0

The Danger of Infinite Recursion

If the base case is omitted… the execution stack will overflow. What happens if we run a recursive function without a base case? Let’s predict!

function infinite() {
  return infinite();
}
// infinite(); // Causes stack overflow

The // infinite() call was commented out to save your browser. If you uncommented it, the runtime would abort execution, throwing a Maximum call stack size exceeded error.

The Call Stack and Unwinding

When the current function finishes, the interpreter takes it off the stack and resumes execution where it left off in the last code listing.

Each time a function calls itself, execution of the current function pauses, and a new execution context is pushed to the call stack. Once the base case is hit, the stack “unwinds”. This means the code after the recursive call gets executed in reverse order (Last In, First Out).

Run this code and predict the output to see unwinding in action:

function climb(steps) {
  if (steps === 0) {
    console.log('Top!');
    return;
  }
  console.log('Up ' + steps);
  climb(steps - 1);
  console.log('Down ' + steps);
}
climb(2);

Up 2
Up 1
Top!
Down 1
Down 2

Using Recursion to Accumulate Results

Often, recursion is used to aggregate data (like multiplying a sequence of numbers). A function can call itself… returning the result of the recursive call is critical. If you forget to return the result of the recursive call, the accumulated value will be lost, and the outer function will return undefined.

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(3));

6

Mastering recursion is a core skill that makes traversing trees, nested objects, and graphs significantly easier!