Recursion Explained

Every recursive function is two things: a case small enough to answer outright, and a step that makes the problem smaller. Miss either one and it never ends.

The two parts

The base case is the input you can answer without recursing. The recursive case calls the function again on something smaller, and trusts it to work.

That trust is the part people struggle with. You do not trace the whole thing in your head. You assume the smaller call is correct and check that you combine its answer properly.

function factorial(n) {
  if (n <= 1) return 1          // base case
  return n * factorial(n - 1)   // smaller, then combine
}

function sumList(items, i = 0) {
  if (i === items.length) return 0        // base case: nothing left
  return items[i] + sumList(items, i + 1) // one item, plus the rest
}

console.log(factorial(5))            // 120
console.log(sumList([1, 2, 3, 4]))   // 10

What the call stack is doing

Each call is paused while the one inside it runs. factorial(5) cannot return until factorial(4) does, and so on down to the base case. Then the answers unwind back up.

That pile of paused calls is the call stack, and it is finite. Recurse too deep and JavaScript throws:

function countDown(n) {
  if (n === 0) return 0
  return countDown(n - 1)
}

countDown(10000)     // fine
countDown(1000000)   // RangeError: Maximum call stack size exceeded

The limit is roughly ten thousand frames in most browsers. JavaScript engines do not reliably optimise tail calls, so you cannot count on that escape hatch - if depth scales with input size, use a loop or an explicit stack.

The mistake that costs the most

Naive recursion can redo enormous amounts of work:

// Exponential. fib(40) makes over 300 million calls.
function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
}

// Linear. Remember what you already worked out.
function fibMemo(n, cache = new Map()) {
  if (n <= 1) return n
  if (cache.has(n)) return cache.get(n)

  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache)
  cache.set(n, result)
  return result
}

console.log(fib(10))      // 55
console.log(fibMemo(30))  // 832040 — instant, unlike fib(30)

That cache is memoisation, and it is the entire idea behind dynamic programming later in this tutorial. The recursion did not change - only the fact that it stopped recomputing.

When to use it

• The data is nested - trees, folders, nested objects, the DOM.
• The problem splits into the same problem, smaller - sorting halves, searching subtrees.
• You are exploring options and may need to undo - backtracking.

For a flat list, a loop is clearer and has no depth limit. Recursion is not a virtue in itself.