Recursion and the Call Stack
A function that calls itself. The idea is small; the skill is trusting the recursive call and getting the base case right. Everything in part two depends on this.
By the end: Write and trace a recursive function without guessing.
A recursive function calls itself on a smaller version of the same problem. Everything in part two of this course — trees, graphs, backtracking, dynamic programming — is built on it, so this is the lesson to get properly comfortable with.
The idea is small. The skill is trusting the recursive call instead of trying to trace it in your head.
function countdown(n) {
if (n === 0) { // base case: nothing left to do
console.log('liftoff');
return;
}
console.log(n);
countdown(n - 1); // recursive case: same problem, smaller
}
countdown(4);Output
What the machine is actually doing
Each call gets its own frame on the call stack, holding its own parameters and local variables. The frame stays there, paused, until the call it is waiting on returns. Seeing this once removes most of the confusion.
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 rest = factorial(n - 1, depth + 1); // pause here until it returns
const result = n * rest;
console.log(`${pad}factorial(${n}) returns ${n} * ${rest} = ${result}`);
return result;
}
console.log('answer:', factorial(4));Output
Read the indentation. Everything goes down to the base case first, and only then do the answers come back up, multiplying on the way. The work happens on the way out, not on the way in.
The three questions
For any recursive problem, answer these in order and the code writes itself.
- What is the smallest input I can answer without recursing? That is the base case.
- How do I make the input smaller? Usually
n - 1, or half, or "the rest of the list", or "each child". - Given the answer to the smaller problem, how do I build my answer? That is the combine step.
// Sum a list. Base: empty is 0. Smaller: drop the first. Combine: add it back.
const sumList = (a, i = 0) => i === a.length ? 0 : a[i] + sumList(a, i + 1);
// Reverse a string. Base: '' is ''. Smaller: drop the first. Combine: append it.
const reverse = (s) => s === '' ? '' : reverse(s.slice(1)) + s[0];
// Is it a palindrome? Base: 0 or 1 chars. Smaller: strip both ends.
const isPal = (s) => s.length <= 1 ? true : s[0] === s[s.length - 1] && isPal(s.slice(1, -1));
// Power. Base: exponent 0 is 1. Smaller: exponent - 1.
const power = (base, exp) => exp === 0 ? 1 : base * power(base, exp - 1);
console.log('sumList([1,2,3,4]):', sumList([1, 2, 3, 4]));
console.log('reverse("recursion"):', reverse('recursion'));
console.log('isPal("racecar"):', isPal('racecar'), '| isPal("hello"):', isPal('hello'));
console.log('power(2, 10):', power(2, 10));Output
Passing state down, or building it up
Two styles. Either you carry an accumulator down through the calls, or each call returns a value that gets combined on the way back. Knowing both, and when each is natural, is worth a lot.
// Build up on the way OUT: each call returns a value, the caller combines.
function flattenReturn(arr) {
const out = [];
for (const item of arr) {
if (Array.isArray(item)) out.push(...flattenReturn(item)); // combine
else out.push(item);
}
return out;
}
// Carry state DOWN: pass the output array in, everyone writes to it.
function flattenAccumulate(arr, out = []) {
for (const item of arr) {
if (Array.isArray(item)) flattenAccumulate(item, out); // no return needed
else out.push(item);
}
return out;
}
const nested = [1, [2, [3, [4, [5]]]], 6];
console.log('returning: ', flattenReturn(nested));
console.log('accumulating:', flattenAccumulate(nested));Output
const sharedOut = [];
function buggy(arr) {
for (const x of arr) Array.isArray(x) ? buggy(x) : sharedOut.push(x);
return sharedOut;
}
console.log('first call: ', buggy([1, [2]]));
console.log('second call:', buggy([3, [4]]), '← leftovers from the first call');
function fixed(arr, out = []) {
for (const x of arr) Array.isArray(x) ? fixed(x, out) : out.push(x);
return out;
}
console.log('fixed first: ', fixed([1, [2]]));
console.log('fixed second:', fixed([3, [4]]));Output
Two branches: where the cost explodes
One recursive call per level is linear. Two calls per level doubles the work at each step, and that is exponential. The naive Fibonacci is the standard demonstration and it matters because it is the doorway to dynamic programming.
let calls = 0;
function fib(n) {
calls++;
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // two branches
}
for (const n of [5, 10, 20, 25]) {
calls = 0;
const value = fib(n);
console.log(`fib(${String(n).padStart(2)}) = ${String(value).padStart(6)} took ${calls.toLocaleString('en-US')} calls`);
}Output
const timesComputed = new Map();
function fibCounted(n) {
timesComputed.set(n, (timesComputed.get(n) ?? 0) + 1);
if (n <= 1) return n;
return fibCounted(n - 1) + fibCounted(n - 2);
}
fibCounted(12);
console.log('fib(12) computed each subproblem this many times:');
for (const n of [...timesComputed.keys()].sort((a, b) => a - b)) {
console.log(` fib(${String(n).padStart(2)}) computed ${timesComputed.get(n)} times`);
}Output
fib(2) is computed dozens of times, and every one of those recomputes the whole subtree beneath it. Nothing about the answer changes between calls, so all of that is waste.
function fibMemo(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n); // already known
const value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, value);
return value;
}
let memoCalls = 0;
function fibMemoCounted(n, memo = new Map()) {
memoCalls++;
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const v = fibMemoCounted(n - 1, memo) + fibMemoCounted(n - 2, memo);
memo.set(n, v);
return v;
}
for (const n of [10, 25, 40, 80]) {
memoCalls = 0;
const v = fibMemoCounted(n);
console.log(`fib(${String(n).padStart(2)}) = ${String(v).padStart(22)} took ${memoCalls} calls`);
}Output
Recursion depth is a hard limit
function depth(n) {
try { return depth(n + 1); }
catch (err) { return n; }
}
console.log('this engine overflows at roughly', depth(0).toLocaleString('en-US'), 'frames');
// So a recursion over 100,000 items will crash even though it is O(n).
function sumRecursive(a, i = 0) {
if (i === a.length) return 0;
return a[i] + sumRecursive(a, i + 1);
}
const big = Array.from({ length: 100000 }, () => 1);
try {
console.log('recursive sum:', sumRecursive(big));
} catch (err) {
console.log('recursive sum failed:', err.name, '— the input was too deep');
}
// The iterative version has no depth limit at all.
let total = 0;
for (const x of big) total += x;
console.log('iterative sum:', total);Output
Recursion on trees, where it is genuinely the best tool
A tree is recursive by definition: each child is itself a tree. This is where recursive code is shorter and clearer than the alternative, and it is why lesson 14 leans on it.
const tree = {
val: 5,
left: { val: 3, left: { val: 1, left: null, right: null }, right: { val: 4, left: null, right: null } },
right: { val: 8, left: null, right: { val: 9, left: null, right: null } },
};
// Height: 0 for nothing, otherwise 1 more than the taller child.
const height = (n) => n === null ? 0 : 1 + Math.max(height(n.left), height(n.right));
// Sum: 0 for nothing, otherwise my value plus both sides.
const sum = (n) => n === null ? 0 : n.val + sum(n.left) + sum(n.right);
// Count leaves: a node with no children is 1.
const leaves = (n) => n === null ? 0 : (n.left === null && n.right === null) ? 1 : leaves(n.left) + leaves(n.right);
console.log('height:', height(tree));
console.log('sum: ', sum(tree));
console.log('leaves:', leaves(tree));
console.log('empty tree height:', height(null));Output
Each is the three questions again. Base case: null. Smaller problem: the children. Combine: max, or add, or add. Once you see that shape, most tree questions take a minute.
Turning recursion into iteration
Any recursion can be rewritten with an explicit stack, because that is all the call stack is. You need this when the depth is too great, and interviewers sometimes ask for it directly.
const tree = { val: 1, left: { val: 2, left: { val: 4 }, right: { val: 5 } }, right: { val: 3 } };
function recursive(node, out = []) {
if (!node) return out;
out.push(node.val);
recursive(node.left, out);
recursive(node.right, out);
return out;
}
function withStack(root) {
const out = [], stack = [root];
while (stack.length) {
const node = stack.pop();
if (!node) continue;
out.push(node.val);
stack.push(node.right); // right first, so left pops first
stack.push(node.left);
}
return out;
}
// And a queue instead of a stack gives level order rather than depth order.
function withQueue(root) {
const out = [], queue = [root];
let head = 0;
while (head < queue.length) {
const node = queue[head++];
if (!node) continue;
out.push(node.val);
queue.push(node.left);
queue.push(node.right);
}
return out;
}
console.log('recursive (depth-first):', recursive(tree));
console.log('stack (depth-first):', withStack(tree));
console.log('queue (breadth-first):', withQueue(tree));Output
Divide and conquer
A particular shape of recursion: split the input roughly in half, solve both halves, combine. When the split is even, the depth is log n and the total work is O(n log n). This is merge sort, quicksort and binary search.
function maxDivide(arr, lo = 0, hi = arr.length - 1, depth = 0) {
if (lo === hi) return arr[lo]; // base: one element
const mid = Math.floor((lo + hi) / 2);
const left = maxDivide(arr, lo, mid, depth + 1); // solve half
const right = maxDivide(arr, mid + 1, hi, depth + 1);// solve the other half
return Math.max(left, right); // combine
}
console.log('max:', maxDivide([3, 7, 1, 9, 4, 2]));
// Depth grows like log2(n): each level halves the remaining size.
function measureDepth(n) {
let d = 0, size = n;
while (size > 1) { size = Math.ceil(size / 2); d++; }
return d;
}
for (const n of [8, 1000, 1000000]) {
console.log('n =', String(n).padStart(7), '→ recursion depth about', measureDepth(n));
}Output
Your turn: five recursive functions
Write each one recursively, with no loops. State the base case in a comment first.
countDigits(n)— how many digits in a non-negative integer.countDigits(9)is 1,countDigits(4502)is 4.gcd(a, b)— greatest common divisor. Euclid:gcd(a, b) === gcd(b, a % b), andgcd(a, 0) === a.binaryString(n)— the binary representation as a string, without usingtoString(2).subsets(arr)— every subset. For each element there are two choices, include it or not, so there are2ⁿresults.deepCount(value)— count all non-array values inside an arbitrarily nested array.
Output
Recap
- Every recursive function needs a base case and a step that genuinely shrinks the input.
- Trust the recursive call: assume it is correct for the smaller input and only work out how to combine.
- Answer three questions — smallest input, how to shrink, how to combine — and the code follows.
- Two recursive calls per level means exponential work; memoising the results makes it linear, and that is dynamic programming.
- Recursion costs
O(depth)stack space and JavaScript has no tail-call optimisation, so deep inputs need a loop or an explicit stack. A stack gives depth-first, a queue gives breadth-first.