Recursion explained, with the call stack printed out

Recursion is a function that calls itself. It needs two parts: a base case that returns without recursing, and a recursive case that calls itself with a smaller version of the problem. Without a base case it never stops, and the program crashes.

function countdown(n) {
  if (n === 0) {
    console.log("liftoff");
    return; // base case
  }
  console.log(n);
  countdown(n - 1); // recursive case, smaller each time
}

countdown(3);

3
2
1
liftoff

That is the mechanism. The reason recursion feels hard is not the definition, it is that you cannot see what is happening. So this post prints it.

Watch the stack build and unwind

Every function call in JavaScript goes onto the call stack, a pile of paused functions. A recursive call is nothing special: it just puts another copy of the same function on the pile. Here is factorial with the depth printed as indentation:

function factorial(n, depth = 0) {
  const pad = "  ".repeat(depth);
  console.log(`${pad}factorial(${n}) called`);

  if (n <= 1) {
    console.log(`${pad}factorial(${n}) returns 1  <- base case`);
    return 1;
  }

  const result = n * factorial(n - 1, depth + 1);
  console.log(`${pad}factorial(${n}) returns ${result}`);
  return result;
}

factorial(4);

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      factorial(1) returns 1  <- base case
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

Read the shape. Every call goes in before any call comes back out. factorial(4) cannot finish its multiplication until factorial(3) gives it a number, which is waiting on factorial(2), and so on down.

Then the base case returns 1, and the whole pile unwinds in reverse: 1, then 2, then 6, then 24. Four calls stacked up, four returns coming back.

That V shape, all the way down and then all the way back, is what a recursive function does. If you can picture that, you understand recursion.

What happens with no base case

function runaway(n) {
  return runaway(n + 1); // nothing ever stops this
}

runaway(0);

RangeError: Maximum call stack size exceeded

The stack is a fixed-size region of memory. Every waiting call takes a slot, nothing ever returns, and eventually there is no room.

The number of slots is not infinite and it is not huge. Counting frames until the throw, on Node v24.14.1:

depth reached before throwing: 12486

About twelve thousand. That is the real ceiling, and it varies by engine, by how many arguments and local variables each frame holds, and by browser. Treat "roughly ten thousand" as the working number.

This matters for correct code too, not just infinite loops. Summing 1 to n recursively is perfectly valid:

function sumTo(n) {
  if (n === 0) return 0;
  return n + sumTo(n - 1);
}

sumTo(100);   // 5050
sumTo(50000); // RangeError: Maximum call stack size exceeded

The loop version has no such limit:

function sumToLoop(n) {
  let total = 0;
  for (let i = 1; i <= n; i += 1) total += i;
  return total;
}

sumToLoop(50000); // 1250025000

A recursive function whose depth grows with your input size has a hard limit on your input size. Some languages avoid this with tail-call optimisation, where a call in the final position reuses the current frame. JavaScript engines broadly do not implement it, so do not count on it.

The expensive kind of recursion

Depth is one cost. Repeated work is the other, and it is worse.

Naive Fibonacci is the standard example, and the standard example undersells it:

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

Counting every call:

Going from n=30 to n=35 added five to the input and eleven times the work. Roughly, each step up multiplies the calls by about 1.6, which is exponential growth, O(2ⁿ) in Big O terms.

The waste is duplication. fib(30) computes fib(28) twice, fib(27) three times, fib(26) five times, and it never remembers any of them. Nearly thirty million calls to compute a number a person could reach with a pen.

Memoisation: the fix in three lines

Cache each result the first time you compute it:

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

Same function, same recursion, one object. Measured on the same run:

Twenty-nine million calls down to sixty-nine. This is not a micro-optimisation, it is a different algorithm wearing the same shape, and it is the entry point to dynamic programming.

When recursion is genuinely the right tool

Given the ceiling and the risk of repeated work, when should you use it? When the data itself is nested and you do not know how deep it goes.

A file tree is the canonical case. A folder holds files and folders, which hold files and folders. There is no loop that handles arbitrary depth without effectively rebuilding a stack yourself.

function listFiles(node, prefix = "") {
  const results = [];
  const path = prefix ? `${prefix}/${node.name}` : node.name;

  if (node.children.length === 0) {
    results.push(path); // base case: a leaf
    return results;
  }

  for (const child of node.children) {
    results.push(...listFiles(child, path)); // recursive case
  }
  return results;
}

Run against a nested structure four levels deep:

[
  "src/index.js",
  "src/components/Button.jsx",
  "src/components/forms/Input.jsx",
  "src/components/forms/Select.jsx"
]

The function has no idea how deep it went, and does not need to. That is the payoff.

Real examples of the same shape: walking the DOM, traversing a JSON response of unknown structure, rendering nested comment threads, searching a binary tree, and every directory-walking script you will ever write.

Recursion or a loop?

Anything recursive can be rewritten as a loop, and anything iterative can be written recursively. The choice is about which one states the problem more clearly, plus the stack ceiling as a hard constraint.

For flat data a loop is clearer and unbounded. For nested data recursion is dramatically clearer, and depth is usually bounded by the data, since a folder tree nested twelve thousand deep is not a real thing.

Turning recursion into a loop, when you have to

Since the stack ceiling is real, it is worth knowing the escape hatch: every recursive function can be rewritten as a loop with an explicit stack. You are not removing the stack, you are moving it from the engine's memory into an array you control, and an array can hold far more than twelve thousand items.

Here is the same file-tree walk as above, written iteratively:

function listFiles(root) {
  const results = [];
  const stack = [{ node: root, prefix: "" }];

  while (stack.length > 0) {
    const { node, prefix } = stack.pop();
    const path = prefix ? `${prefix}/${node.name}` : node.name;

    if (node.children.length === 0) {
      results.push(path);
      continue;
    }
    // pushed in reverse so the first child comes off the stack first
    for (let i = node.children.length - 1; i >= 0; i -= 1) {
      stack.push({ node: node.children[i], prefix: path });
    }
  }
  return results;
}

Run against the same tree, both versions produce byte-identical output. The difference shows up on depth. Built a chain 100,000 levels deep and ran both:

recursive: RangeError - Maximum call stack size exceeded
iterative: survived

The trade is honest: the iterative version is longer, the reverse-order push is a detail that is easy to get wrong, and the recursive version reads better. So write the recursive one by default, and reach for this when the depth is genuinely unbounded, such as walking a directory tree on a machine you do not control.

Notice what the rewrite reveals. The stack array holds exactly what the call stack was holding: the node to process and the state to process it with. Recursion was never magic; the engine was keeping this array for you.

Writing one without getting stuck

The trick is to stop tracing. Nobody usefully holds twelve nested calls in their head, and trying to is what makes recursion feel impossible.

1. Write the base case first. What is the smallest input with an obvious answer? Empty array, zero, a node with no children. Handle it and return.

2. Assume the recursive call already works. This is the leap. When writing factorial(n), trust that factorial(n - 1) returns the right answer. Do not verify it mentally. If your base case is right and each call gets smaller, it does work.

3. Make sure the input shrinks. Every recursive call must move toward the base case. n - 1, arr.slice(1), node.children. If a call can happen with the same input, you have written runaway.

4. Combine. Take what the recursive call returned and do the one step this level is responsible for. For factorial that is n * (result from below).

That is the whole method, and step 2 is the one people skip. Recursion becomes manageable the moment you stop trying to follow it all the way down and start trusting the smaller call.

Debugging it

Three habits that turn a mystery into a fix.

• Print the depth. Pass a depth parameter and indent your logs by it, as in the factorial example above. The V shape appears immediately, and a missing base case is obvious because there is no bottom.
• Read RangeError: Maximum call stack size exceeded as "no base case, or the input is not shrinking". Those are almost always the two causes. Check the shrink step first.
• Count calls before optimising. A counter incremented at the top of the function tells you whether you have a depth problem or a repeated-work problem, and they have different fixes.

Trace one yourself

Recursion clicks when you watch the stack build and unwind rather than reading that it does. The factorial trace above is eight lines of output that replace an hour of confusion, and it is worth typing rather than skimming.

DSA Basics covers recursion, the call stack and memoisation with the code running in your browser and the trace printing live, so the V shape is something you produce.

Related reading: Big O Notation Explained for why naive Fibonacci is O(2ⁿ) and what that costs, JavaScript Closures Explained because each recursive call gets its own scope and that is why the parameters do not collide, and Async Await Explained for the other way JavaScript pauses and resumes functions.