After this lesson you can write a function that calls itself, explain how it stops, and use it on nested data. Recursion has a reputation for being confusing. It is simpler than it looks if you always check two things: where it stops, and how each call gets closer to stopping.
What recursion is
Recursion is when a function calls itself. It solves a problem by splitting it into a smaller version of the same problem, again and again, until the problem is so small that the answer is obvious.
Here is a countdown:
function countdown(n) {
if (n === 0) {
console.log("Go!");
return;
}
console.log(n);
countdown(n - 1);
}
countdown(3);
// 3
// 2
// 1
// Go!Two parts make it work:
- The base case.
if (n === 0)is the stopping point. It does not callcountdownagain. - The recursive case. Otherwise the function does a little work and calls itself with
n - 1, a smaller input.
If you forget the base case, or the input never gets closer to it, the function calls itself forever.
Factorial: the classic example
The factorial of a number, written n!, is the product of all whole numbers from n down to 1. So 4! = 4 × 3 × 2 × 1 = 24. Notice that 4! = 4 × 3!. The problem contains a smaller copy of itself:
function factorial(n) {
if (n <= 1) {
return 1; // base case
}
return n * factorial(n - 1); // recursive case
}
console.log(factorial(4)); // 24
console.log(factorial(5)); // 120Trace factorial(3) by hand:
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * 1)
= 6The calls go down until the base case answers, then the answers come back up and are multiplied on the way. Try the same idea in the editor, with each call writing its depth so you can see the shape:
<pre id="out"></pre>
<script>
const out = document.getElementById("out");
function show(text) {
out.textContent += text + "\n";
}
function factorial(n, depth = 0) {
const pad = " ".repeat(depth);
show(pad + "factorial(" + n + ")");
if (n <= 1) {
show(pad + "base case, returns 1");
return 1;
}
const result = n * factorial(n - 1, depth + 1);
show(pad + "returns " + result);
return result;
}
factorial(4);
</script>The call stack
Each time a function is called, JavaScript remembers where to return to, on a structure called the call stack. In factorial(4), four calls wait on the stack at the deepest point. The stack has a limit. If recursion goes too deep, which usually means a missing or unreachable base case, you get an error:
function forever(n) {
return forever(n + 1);
}
try {
forever(0);
} catch (error) {
console.log(error.name); // RangeError
}The error is RangeError: Maximum call stack size exceeded. The exact depth limit depends on the engine and is not something to rely on.
Recursion over a list
The sum of a list is the first item plus the sum of the rest:
function sum(numbers) {
if (numbers.length === 0) {
return 0; // base case: empty list
}
const [first, ...rest] = numbers; // see Rest and spread
return first + sum(rest);
}
console.log(sum([1, 2, 3, 4])); // 10Each call works on a shorter list, so it must eventually reach the empty list. This uses the rest syntax from the Rest and spread lesson. For a plain list a loop (or reduce) is simpler and faster; the example is here to show the pattern.
Where recursion really helps: nested data
Recursion fits data whose items can contain items of the same kind, such as folders inside folders, comment threads, menus or a family tree. You often do not know how deep the nesting goes, so a fixed number of loops cannot cover it.
const folder = {
name: "root",
children: [
{ name: "a.txt", children: [] },
{
name: "docs",
children: [
{ name: "b.txt", children: [] },
{ name: "images", children: [{ name: "c.png", children: [] }] }
]
}
]
};
function countItems(node) {
let total = 1; // count this item
for (const child of node.children) {
total += countItems(child); // the same logic for each child
}
return total;
}
console.log(countItems(folder)); // 6The items are the root, a.txt, docs, b.txt, images and c.png, so the answer is 6. The base case is hidden: an item with an empty children list makes no further calls, so the loop body never runs for it. The same function works however deep the folders go.
Recursion versus loops
Anything you can do with recursion you can do with a loop, and vice versa. Choose by clarity:
- Loops use constant memory and are fast. Use them for flat, repeated work such as totals and counters.
- Recursion reads more clearly when the problem is naturally nested or has a "same problem, smaller size" shape.
JavaScript does not guarantee tail-call optimisation across engines, so do not rely on very deep recursion, such as tens of thousands of levels, being safe.
Common mistakes
No base case. The function never stops and ends in a RangeError.
A base case that is never reached. countdown(n - 1) is fine; countdown(n + 1) moves away from zero. Check the direction of every call.
Forgetting to return the recursive call. Writing factorial(n - 1) without n * or return loses the result and gives undefined.
Using recursion for huge inputs. A recursive sum of a million-item array will overflow the stack. Use a loop.
Repeating work. A naive recursive Fibonacci function recomputes the same values many times and gets very slow. Store results you have already computed, or use a loop.
Exercise
Write a recursive function power(base, exponent) that returns base raised to a whole exponent, with power(2, 0) as the base case returning 1. Then write reverse(text) that returns a string reversed: the base case is the empty string; otherwise return reverse of everything after the first character, followed by the first character. Test with "hello". As a stretch, write flatten(list) that turns [1, [2, [3, 4]], 5] into [1, 2, 3, 4, 5].
That finishes the Functions section. Next you will start storing collections of data in Arrays.
Key points
- A recursive function is one that calls itself to solve a smaller version of the same problem.
- Every recursive function needs a base case that stops the calls, or it runs until the stack overflows.
- Each call must move closer to the base case, for example by working with a smaller number or shorter list.
- Recursion fits naturally with nested data such as folders, menus and trees.
- Any recursion can be written as a loop; loops use less memory, while recursion can read more clearly.