JS-201 · Lesson 6 of 12 · 25 min
Recursion
▶ Video coming soon A video version of this lesson is on the way.
The Food Hub's programs are organized like a family tree. The Food Hub has programs, some programs have teams, and some teams have smaller groups, such as the youth cooking group inside the cooking classes. Paul Desrosiers, the executive director, wants the dashboard to show the number of volunteers in any part of that tree, including everything beneath it. At the sixth session, on Thursday, September 23, Mira tries to write it with loops and finds she needs a loop inside a loop inside a loop, with no way of knowing how deep to go. Gareth suggests a function that calls itself.
A function that calls itself
A recursive function solves a problem by calling itself on a smaller version of the same problem. Every recursive function has two parts. The base case is an input small enough to answer directly, without another call. The recursive case breaks the input into a smaller piece, calls the function on that piece and builds the answer from the result. As long as every recursive call moves closer to a base case, the calls eventually stop.
The classic first example is the factorial, written n!, which is the product of the whole numbers from 1 to n. It has a natural recursive definition: 0! is 1, and for any larger n, n! is n times (n − 1)!. The function below is that definition, word for word.
function factorial(n) {
if (n === 0) return 1; // base case
return n * factorial(n - 1); // recursive case: a smaller problem
}
console.log(factorial(0), factorial(1), factorial(5), factorial(10));1 1 120 3628800
What this code does
factorial returns 1 straight away when n is 0, which is the base case. For any other n it multiplies n by the factorial of n minus 1, so each call works on a smaller number until it reaches 0. factorial(5) therefore becomes 5 × 4 × 3 × 2 × 1 × 1, which is 120.
It helps to read a recursive function by trusting it, a habit sometimes called the recursive leap of faith. Assume factorial(n − 1) returns the right answer, and check only two things: that the base case is right, and that the recursive case builds the right answer from a correct smaller answer. If both hold, the function is correct for every n, by the same reasoning as a proof by induction in mathematics.
What happens on the call stack
Recursion is not special to the engine. Each call to factorial is an ordinary function call, so it pushes a new frame onto the call stack, holding that call's own n and the place to return to. The calls pile up until the base case returns, and then the frames come off one at a time, each finishing its multiplication with the value returned by the call above it.
function factorial(n, depth = 0) {
const pad = ' '.repeat(depth);
console.log(pad + 'factorial(' + n + ') called');
if (n === 0) { console.log(pad + 'base case returns 1'); return 1; }
const result = n * factorial(n - 1, depth + 1);
console.log(pad + 'factorial(' + n + ') returns ' + result);
return result;
}
factorial(3);factorial(3) called
factorial(2) called
factorial(1) called
factorial(0) called
base case returns 1
factorial(1) returns 1
factorial(2) returns 2
factorial(3) returns 6What this code does
The extra depth argument only controls the indentation, so each nested call is printed further to the right. The output shows every call being made before any of them finishes, then the results coming back in reverse order. That pattern is the call stack growing to four frames and then shrinking again.
Each frame takes memory, so a recursive function whose depth grows with n uses O(n) stack space, even if it creates no arrays. factorial(10) needs eleven frames at once; a function that recursed once for each of 100,000 records would need 100,000.
Recursion on nested data
Recursion is most useful when the data itself is recursive: a structure that contains smaller structures of the same kind. Paul's program tree is one. Each node has a name, a number of volunteers who belong to it directly, and an array of children, each of which is itself a program node. The total for a node is its own volunteers plus the total of each child, and that definition is recursive in exactly the same way as factorial.
const foodHub = {
name: 'Food Hub', volunteers: 4, children: [
{ name: 'Grocery program', volunteers: 22, children: [
{ name: 'Warehouse', volunteers: 9, children: [] },
{ name: 'Pick-up desk', volunteers: 14, children: [] },
] },
{ name: 'Community kitchen', volunteers: 6, children: [
{ name: 'Lunch counter', volunteers: 12, children: [] },
{ name: 'Cooking classes', volunteers: 5, children: [
{ name: 'Youth cooking', volunteers: 3, children: [] },
] },
] },
{ name: 'Youth garden', volunteers: 18, children: [] },
],
};
function totalVolunteers(node) {
let total = node.volunteers;
for (const child of node.children) total += totalVolunteers(child);
return total;
}
console.log('whole Food Hub:', totalVolunteers(foodHub));
console.log('community kitchen:', totalVolunteers(foodHub.children[1]));
console.log('youth garden:', totalVolunteers(foodHub.children[2]));whole Food Hub: 93 community kitchen: 26 youth garden: 18
What this code does
totalVolunteers adds a node's own volunteers to the totals of all its children, found by calling itself on each child. A node with no children is the base case, because the loop does nothing and the function just returns its own count. The function works for a tree of any depth without knowing the depth in advance.
The base case here is hidden: a node with an empty children array makes no recursive calls. That is common with trees. The function visits every node once, so it is O(n) in the number of nodes, and its stack depth is the depth of the tree, which is four here.
The same shape handles other questions about the tree: listing every program with its level of indentation, finding the deepest group or searching for a program by name. Each is a function that does something with the node and then calls itself on each child.
const foodHub = {
name: 'Food Hub', volunteers: 4, children: [
{ name: 'Grocery program', volunteers: 22, children: [
{ name: 'Warehouse', volunteers: 9, children: [] },
{ name: 'Pick-up desk', volunteers: 14, children: [] },
] },
{ name: 'Community kitchen', volunteers: 6, children: [
{ name: 'Lunch counter', volunteers: 12, children: [] },
{ name: 'Cooking classes', volunteers: 5, children: [
{ name: 'Youth cooking', volunteers: 3, children: [] },
] },
] },
{ name: 'Youth garden', volunteers: 18, children: [] },
],
};
function outline(node, level = 0) {
const lines = [' '.repeat(level) + node.name];
for (const child of node.children) lines.push(...outline(child, level + 1));
return lines;
}
function depth(node) {
if (node.children.length === 0) return 1;
return 1 + Math.max(...node.children.map(depth));
}
console.log(outline(foodHub).join('\n'));
console.log('levels:', depth(foodHub));Food Hub
Grocery program
Warehouse
Pick-up desk
Community kitchen
Lunch counter
Cooking classes
Youth cooking
Youth garden
levels: 4What this code does
outline returns the node's name, indented by its level, followed by the outlines of all its children, so the output reads like a table of contents. depth returns 1 for a node with no children, and otherwise 1 more than its deepest child. Both functions visit each node once.
Limits on depth
The call stack has a limited size. If recursion goes too deep, Chrome, Edge, Safari and Node.js stop the program with a RangeError whose message is "Maximum call stack size exceeded"; Firefox throws an InternalError with the message "too much recursion". The limit is not part of the JavaScript standard. It depends on the engine, the device and how much each frame holds, and on desktop browsers it is typically in the region of ten thousand frames. A recursive function that goes one level deeper for each item in a list is therefore a risk for long lists.
function countDown(n) {
if (n === 0) return 'done';
return countDown(n - 1);
}
console.log(countDown(1000));
try {
countDown(1000000);
} catch (e) {
console.log(e.name + ':', e.message);
}done RangeError: Maximum call stack size exceeded
What this code does
countDown calls itself once for every number, so its stack depth equals n. A thousand frames are no problem, but a million exceed the engine's limit, and the engine throws an error instead of freezing. The output shown is from Chrome; Firefox words the error differently. The exact limit varies between devices, so code should not depend on it.
Some languages remove this limit for tail calls, where the recursive call is the very last thing a function does, as in countDown. The ECMAScript 2015 standard asked for proper tail calls in strict mode, but only Safari's engine implements them; Chrome, Edge, Firefox and Node.js do not. In practice, JavaScript code must not rely on tail calls, and recursion whose depth grows with the size of the data should be rewritten as a loop when the data can be large.
Recursion and loops
Every recursive function can be rewritten as a loop, and every loop as recursion. When the recursion makes one call per step, as factorial and countDown do, the loop version is simple and usually better. When the recursion branches, as totalVolunteers does over each child, the loop version needs its own explicit stack to remember the nodes still to visit, which is exactly what the call stack was doing for free.
const foodHub = {
name: 'Food Hub', volunteers: 4, children: [
{ name: 'Grocery program', volunteers: 22, children: [
{ name: 'Warehouse', volunteers: 9, children: [] },
{ name: 'Pick-up desk', volunteers: 14, children: [] },
] },
{ name: 'Community kitchen', volunteers: 6, children: [
{ name: 'Lunch counter', volunteers: 12, children: [] },
{ name: 'Cooking classes', volunteers: 5, children: [
{ name: 'Youth cooking', volunteers: 3, children: [] },
] },
] },
{ name: 'Youth garden', volunteers: 18, children: [] },
],
};
function totalVolunteersLoop(root) {
let total = 0;
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
total += node.volunteers;
for (const child of node.children) stack.push(child);
}
return total;
}
console.log(totalVolunteersLoop(foodHub));93
What this code does
The loop version keeps an array as a stack of nodes still to count. It pops a node, adds its volunteers and pushes its children, and stops when the stack is empty. The answer matches the recursive version, and because the stack is an ordinary array on the heap, it can grow to millions of nodes without hitting the call stack limit.
Choose by clarity first. For a tree that is a few levels deep, such as the program structure or a page's DOM, recursion is clear and safe. For data whose depth can grow with its size, such as a long linked list, or nested data from an untrusted source, use a loop. structuredClone, which copies nested data, is a built-in example of the careful kind: it copies deep structures and even handles objects that refer back to themselves.
Branching recursion and repeated work
Some recursive definitions make two or more calls each time. The Fibonacci numbers are the standard example: each number is the sum of the two before it, starting from 0 and 1. The recursive definition is short and obviously correct, but it hides a problem, which the call counter below reveals.
let calls = 0;
function fib(n) {
calls++;
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
for (const n of [10, 20, 25]) {
calls = 0;
const value = fib(n);
console.log('fib(' + n + ') =', value, 'took', calls, 'calls');
}fib(10) = 55 took 177 calls fib(20) = 6765 took 21891 calls fib(25) = 75025 took 242785 calls
What this code does
fib calls itself twice for every n of 2 or more, and each of those calls splits again. The counter shows the number of calls growing by a factor of about 1.6 for each step in n, so fib(25) needs nearly a quarter of a million calls. The answers are right, but the work is exponential.
The call tree shows why: fib(5) computes fib(3) twice and fib(2) three times, and the repetition multiplies as n grows. The fix is to remember each answer the first time it is computed, a technique called memoization. With a Map of answers, each fib(k) is computed once, and the whole calculation becomes O(n). Lesson 11 builds on this idea under its more general name, dynamic programming.
let calls = 0;
function fibMemo(n, memo = new Map()) {
calls++;
if (n < 2) return n;
if (memo.has(n)) return memo.get(n);
const value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, value);
return value;
}
for (const n of [10, 25, 70]) {
calls = 0;
console.log('fib(' + n + ') =', fibMemo(n), 'took', calls, 'calls');
}fib(10) = 55 took 19 calls fib(25) = 75025 took 49 calls fib(70) = 190392490709135 took 139 calls
What this code does
fibMemo stores every answer in a Map the first time it works it out, and returns the stored answer on every later call for the same n. Each value is therefore computed once, and the number of calls grows in step with n instead of exponentially. fib(70) is still exact because it is below the largest whole number a JavaScript number can hold precisely.
Recursion that explores choices
Recursion is also the natural way to generate every possibility, a technique called backtracking. To list every group that can be formed from a set of volunteers, decide about the first volunteer, in or out, and recurse on the rest. Each volunteer doubles the number of possibilities, so n volunteers give 2ⁿ groups. That exponential growth is unavoidable when every group really must be listed, and it is why Lesson 11 looks for smarter methods when only the best group is wanted.
function groups(people) {
if (people.length === 0) return [[]]; // one group: the empty one
const [first, ...rest] = people;
const without = groups(rest);
const withFirst = without.map((g) => [first, ...g]);
return [...withFirst, ...without];
}
const drivers = ['Ana', 'Ben', 'Chi'];
const all = groups(drivers);
console.log(all.length, 'groups');
console.log(all.map((g) => '{' + g.join(', ') + '}').join(' '));
console.log('with 20 people:', 2 ** 20, 'groups');8 groups
{Ana, Ben, Chi} {Ana, Ben} {Ana, Chi} {Ana} {Ben, Chi} {Ben} {Chi} {}
with 20 people: 1048576 groupsWhat this code does
groups returns every possible group of the people it is given. For an empty list the only group is the empty one; otherwise it finds all groups of the other people and returns each of them both with and without the first person. Three drivers give eight groups, and every extra person doubles the count, so twenty people give over a million.
| Pattern | Calls per step | Typical cost | Example |
|---|---|---|---|
| Linear recursion | One | O(n) time, O(n) stack | factorial, countDown |
| Tree recursion over data | One per child | O(nodes) time, O(depth) stack | totalVolunteers |
| Divide and conquer | Two on halves | Often O(n log n) | Merge sort, Lesson 7 |
| Branching on overlapping subproblems | Two or more | Exponential unless memoized | Naive fib |
| Backtracking over choices | Two or more | Exponential by nature | Listing every group |
Try it yourself
Add up nested boxes
A hamper is packed as boxes inside boxes. Each box is an array whose items are either weights or more boxes. Complete totalWeight(box) so that it returns the total of all the weights at every level.
Use recursion: a number adds directly, and an array adds its own total.
function totalWeight(box) {
let total = 0;
for (const item of box) {
if (typeof item === 'number') total += item;
}
return total;
}
const hamper = [1200, [400, 400, [250, 250]], 900, [], [[150]]];
console.log(totalWeight(hamper));
console.log(totalWeight([]));Try it yourself
Find a program by name
Complete findProgram(node, name) so that it returns the node whose name matches, searching the node and everything beneath it, or null if there is no such program.
Stop searching as soon as a match is found.
const foodHub = {
name: 'Food Hub', volunteers: 4, children: [
{ name: 'Grocery program', volunteers: 22, children: [
{ name: 'Warehouse', volunteers: 9, children: [] },
{ name: 'Pick-up desk', volunteers: 14, children: [] },
] },
{ name: 'Community kitchen', volunteers: 6, children: [
{ name: 'Lunch counter', volunteers: 12, children: [] },
{ name: 'Cooking classes', volunteers: 5, children: [
{ name: 'Youth cooking', volunteers: 3, children: [] },
] },
] },
{ name: 'Youth garden', volunteers: 18, children: [] },
],
};
function findProgram(node, name) {
if (node.name === name) return node;
return null;
}
console.log(findProgram(foodHub, 'Youth cooking')?.volunteers);
console.log(findProgram(foodHub, 'Warehouse')?.volunteers);
console.log(findProgram(foodHub, 'Bike repair'));Try it yourself
Fast powers
Complete power(x, n) for a whole number n of 0 or more, using recursion that halves n: x⁰ is 1, xⁿ for even n is (x^(n/2))², and for odd n it is x × xⁿ⁻¹. Count the calls in the variable calls.
The halving makes the function O(log n) instead of O(n).
let calls = 0;
function power(x, n) {
calls++;
if (n === 0) return 1;
return x * power(x, n - 1);
}
console.log(power(2, 10), power(3, 5), power(7, 0));
calls = 0;
power(2, 1000);
console.log('calls for n = 1000:', calls);Common mistakes
MistakeWriting a recursive function with no base case.
InsteadEvery recursive function needs an input it answers directly, and every call must move toward it.
MistakeAssuming recursion is fine for any input size.
InsteadDeep recursion throws a RangeError. Use a loop when depth grows with the size of the data.
MistakeRelying on tail calls to avoid stack overflow.
InsteadOnly Safari implements proper tail calls; other engines do not.
MistakeRecursing twice on the same subproblem, as in naive fib.
InsteadMemoize the answers so that each subproblem is solved once.
MistakeChanging shared arrays while recursing over them.
InsteadBuild and return new values, or copy before changing, so calls do not interfere.
Summary and key terms
- A recursive function solves a problem by calling itself on smaller versions of it.
- It needs a base case answered directly and a recursive case that moves toward the base case.
- To check one, trust that the smaller call is right and check the base case and how the answer is built.
- Each call is an ordinary call that adds a frame to the call stack, so recursion depth costs stack space.
- Recursion fits recursive data such as trees, where a function handles a node and then calls itself on each child.
- The call stack is limited, and too deep a recursion throws a RangeError, and most engines do not implement proper tail calls, so recursion whose depth grows with the data should become a loop with an explicit stack.
- Branching recursion on overlapping subproblems, such as naive Fibonacci, repeats work exponentially, and memoization fixes it.
- Backtracking explores every choice and is exponential when all possibilities are needed.
- recursion
- Solving a problem by having a function call itself on smaller instances of the problem.
- base case
- An input a recursive function answers directly, without another recursive call.
- recursive case
- The part of a recursive function that calls itself on a smaller input.
- stack frame
- The record of one function call on the call stack, holding its variables and return point.
- stack overflow
- Running out of call stack space, reported in JavaScript as a RangeError.
- tail call
- A call that is the last action of a function, which some languages can run without a new frame.
- recursive data
- Data that contains smaller pieces of the same kind, such as a tree of programs.
- memoization
- Storing the results of calls so that repeated calls with the same input return the stored result.
- backtracking
- Exploring choices recursively, trying each option and undoing it before trying the next.
- divide and conquer
- Splitting a problem into parts, solving each recursively and combining the results.
Practice problems
Work each problem on paper first, then reveal the answer to check.
What two parts must every recursive function have?
Show answer
A base case answered directly and a recursive case that calls the function on a smaller input.
How much stack space does factorial(n) use?
Show answer
O(n), one frame per call until the base case returns.
Why is naive fib exponential?
Show answer
Each call makes two more calls and the same subproblems are solved many times.
How many groups can be formed from 10 volunteers, counting the empty group?
Show answer
2¹⁰ = 1,024.
When should recursion be replaced by a loop?
Show answer
When its depth grows with the size of the data and the data can be large.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.