9. Recursion and the call stack

A box of boxes

Here is a folder on a computer, written as objects. A folder has a name and a list of things inside it. Some of those things are folders too:

const docs = {
  name: 'docs',
  children: [
    { name: 'a.txt', children: [] },
    { name: 'pics', children: [
      { name: 'cat.png', children: [] },
      { name: 'old', children: [
        { name: 'dog.png', children: [] },
      ] },
    ] },
  ],
};

How many items are there in total? One for loop can visit the children of docs. To reach inside pics you’d need a loop inside that loop, and a third loop for old. But you don’t know how deep the folders go until the program runs. You can’t write “as many nested loops as it takes”.

You can, though, write a function that calls itself.

A function that calls itself

Start smaller than folders. To add up the numbers from 1 to n, notice that the sum up to 3 is just 3 plus the sum up to 2:

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

console.log(sumTo(3)); // 6

Two things make this work. When n is 0 the answer is known straight away, with no further calls. And every other call asks about a smaller n, so the questions are guaranteed to reach 0 eventually.

The call stack

In chapter 1 you learned that each call gets a fresh, private page for its parameters and local variables. Recursion is where that pays off. sumTo(3) and sumTo(2) are both running at once, and each has its own n. JavaScript keeps the pages in a pile: the newest call on top, the calls waiting for it underneath. Step through it:

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

It’s called a stack because it works like a stack of plates: you only ever add to the top or take from the top. The last call to start is always the first to finish.

This little program makes the order visible. Predict the output before you run it:

function down(n) {
  if (n === 0) {
    console.log('bottom');
    return;
  }
  console.log('in ' + n);
  down(n - 1);
  console.log('out ' + n);
}

down(3);

Every in line prints on the way down, as frames are pushed. Every out line prints on the way back up, as they’re popped, so they come out in the reverse order.

When it never stops

What if the base case is missing, or never reached?

function forever(n) {
  return forever(n + 1);
}

forever(0);
// RangeError: Maximum call stack
// size exceeded

Every call pushes another frame, and nothing ever pops. The stack is given a fixed amount of memory, and when it runs out the engine stops the program with an error. That is a stack overflow. Chrome and Safari report it as a RangeError saying “Maximum call stack size exceeded”; Firefox calls it “too much recursion”^[3]. The exact limit depends on the engine.

Trees: recursion’s natural home

Back to the folders. A folder is an object whose children are more folders, and each of those has children of its own. Data shaped like this is a tree, and recursion fits it perfectly, because every child is a smaller tree:

function count(node) {
  let total = 1; // this node
  for (const c of node.children) {
    total = total + count(c);
  }
  return total;
}

console.log(count(docs)); // 6

There’s no explicit if here. The base case hides in the loop: a node with no children runs the loop zero times and returns 1.

Programs are trees too. The expression (2 + 3) * 4 is a multiplication whose left side is an addition:

const tree = {
  kind: 'mul',
  left: {
    kind: 'add',
    left: { kind: 'num', value: 2 },
    right: { kind: 'num', value: 3 },
  },
  right: { kind: 'num', value: 4 },
};

Your turn

The core exercise is a tiny interpreter: it computes the value of an expression tree.

function evaluate(node) {
  // your code here
}

const two = { kind: 'num', value: 2 };
const t = {
  kind: 'add', left: two, right: two,
};
console.log(evaluate(t));

function depth(node) {
  // your code here
}

const leaf = {
  name: 'a', children: [],
};
console.log(depth(leaf));

What you learned

• Recursion is a function calling itself on a smaller problem. It needs a base case that answers directly, and every input must eventually reach it.
• The call stack holds one frame per unfinished call. Calls push frames; returns pop them. The last call to start is the first to finish.
• Endless recursion fills the stack and causes a stack overflow.
• A tree is nodes holding child nodes. Recursion walks it naturally: handle this node, recurse on each child, and stop at the leaves.

Next: strings, up close, one character at a time.