A Functions Existential Crisis

Welcome to recursion, where functions call themselves like lost souls trying to find meaning. We’ll cover what recursion is, how it works, and how to keep your brain from crashing like your code.

What Is Recursion?

A recursive function is one that calls itself as part of its own definition. It solves a problem by breaking it into a smaller version of the same problem until it reaches a case simple enough to answer directly.

Every recursive function needs two things:

1. A base case — the condition that stops the recursion
2. A recursive case — where the function calls itself with a smaller input

function countdown(n) {
  if (n <= 0) {
    console.log("Liftoff!");
    return;
  }
  console.log(n);
  countdown(n - 1); // recursive case
}

countdown(3);
// 3
// 2
// 1
// Liftoff!

The Classic: Factorial

Factorial is the textbook example because its recursive definition mirrors its mathematical one.

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

factorial(5); // 120

Each call waits for the next one to resolve before it can multiply. The call stack grows with each call and collapses on the way back out.

The Stack: Where Recursion Lives and Dies

Every function call pushes a frame onto the call stack. Deep recursion pushes many frames. If you recurse too deeply, you get the most poetic runtime error in programming:

RangeError: Maximum call stack size exceeded

function infinite() { return infinite(); }
infinite(); // RangeError — the function finally found itself, briefly

Thinking Recursively: Fibonacci

The Fibonacci sequence is defined recursively by nature: each number is the sum of the two before it.

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

fib(10); // 55

This is correct but slow — fib(5) is computed many times over. Adding memoization fixes it:

function memoFib(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = memoFib(n - 1, memo) + memoFib(n - 2, memo);
  return memo[n];
}

memoFib(40); // instant

When Recursion Is the Right Tool

Recursion shines when the data or problem is naturally recursive:

• Tree traversal — DOM trees, file systems, JSON with arbitrary depth
• Divide and conquer algorithms — merge sort, binary search
• Parsing — nested expressions, grammars

// Recursively sum all numbers in a nested array
function deepSum(arr) {
  return arr.reduce((acc, item) =>
    acc + (Array.isArray(item) ? deepSum(item) : item), 0);
}

deepSum([1, [2, [3, [4]]]]);  // 10

A loop would need an explicit stack to handle arbitrary nesting. Recursion handles it naturally.

When to Use a Loop Instead

If the input is flat, the depth is bounded, or you need maximum performance — use a loop. Recursion carries overhead: a new stack frame per call, no tail-call optimization in most JS engines outside of strict mode edge cases.

Takeaway

Recursion is not magic — it is a function calling itself with a smaller problem until the problem disappears. Nail the base case, trust the recursive case, and add memoization when performance matters. The function was never lost. It just needed to find a smaller version of itself.