a box inside a box

say there's a key in a box. inside the box there are more boxes, and inside those, more boxes. how do you find it?

one way is a pile: put the box on the pile, take a box off, open it. if there's a box inside, put it on the pile. if it's the key, you're done. that's a loop.

both work. the recursive one reads closer to how you'd say it out loud, and the loop goes easier on memory, for a reason we'll get to.

#base case, recursive case

every recursive function has two parts: the base case, where it stops, and the recursive case, where it calls itself on something smaller. forget the base case, or make it one it never reaches, and it never stops.

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

n <= 1, not n === 1: with === 1, factorial(0) counts down past zero forever, or until it runs out of stack.

recursive data looks like this: a folder full of files and folders.

function countFiles(folder) {
  let count = folder.files.length;
  for (const subfolder of folder.subfolders) count += countFiles(subfolder);
  return count;
}

#the call stack

every call gets a frame on the call stack, holding its arguments and where to go back to when it's done. factorial(4) can't finish until factorial(3) does, so the frames pile up, and the answers come back down as each one returns.

the pile has a limit. on Node 24, a function that only calls itself ran out after 12,524 calls: RangeError: Maximum call stack size exceeded. boxes nested that deep are rare. a list processed one item per call isn't.

some languages get around it with tail calls: when calling itself is the last thing a function does, its frame can be reused. JavaScript's spec has had them since ES2015, and Safari's engine implements them, but V8, the engine in Chrome and Node, doesn't: in Node, summing to a million with a tail-recursive function still blew the stack. in JavaScript, deep recursion means a loop.

#doing the same work twice

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

it's the textbook example, and it's slow, because it solves the same pieces over and over: fibonacci(5) works out fibonacci(3) twice, and each of those works out fibonacci(2) again.

counted: fibonacci(30) makes 1,664,079 calls. fibonacci(40) makes 204,668,309, and took 782ms. remember each answer the first time, and the same fibonacci(30) takes 57 calls:

const memo = new Map();
 
function fibonacci(n) {
  if (n <= 2) return 1;
  if (!memo.has(n)) memo.set(n, fibonacci(n - 1) + fibonacci(n - 2));
  return memo.get(n);
}