Recursion: the base case and the call stack
A recursive function calls itself with a smaller version of its own job. The first thing it needs is a base case, a condition under which it returns without calling itself, because without one the calls never stop. The second is an argument that moves towards that case on every level, so that the base case is reached after a finite number of steps.
JavaScript keeps every unfinished call on the call stack, which is the same stack a debugging tool shows. That is why a recursion without a base case ends in a RangeError rather than in an endless loop, and why the depth a program may reach depends on the machine. This lesson shows the shape, counts the levels, catches the error once to read its message, and ends with the data structure recursion is really for.
A function that calls itself
The factorial of a number is the product of every whole number up to it, and its definition is recursive: the factorial of n is n times the factorial of n - 1, with the factorial of 1 as 1. The function below is that sentence in code, with the base case first.
function factorial(n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
console.log('5! =', factorial(5));
console.log('10! =', factorial(10));
function countDown(n) {
if (n === 0) {
return 'liftoff';
}
return `${n} ${countDown(n - 1)}`;
}
console.log(countDown(5));
node base.js
5! = 120
10! = 3628800
5 4 3 2 1 liftoff
The first call reaches the base case after five levels and then multiplies on the way back, so 5 times 4 times 3 times 2 times 1 is computed from the inside out. The countdown builds its string the same way and prints the numbers in the order a reader expects, because each level put its own number in front of the result of the next. A loop would compute both answers too; recursion is worth its cost when the shape of the data is recursive, which is the last section.
The call stack
Every call that has not returned yet waits on the call stack, and a recursive call adds one frame to it. The function below returns the number of levels it went down, which is the depth of the stack at the moment the base case returned. The number is small here and the arithmetic is trivial, so the frames are the only thing the program is about.
function depth(n) {
if (n === 0) {
return 0;
}
return 1 + depth(n - 1);
}
console.log('depth at 0:', depth(0));
console.log('depth at 5:', depth(5));
console.log('depth at 100:', depth(100));
console.log('depth at 1000:', depth(1000));
node stack.js
depth at 0: 0
depth at 5: 5
depth at 100: 100
depth at 1000: 1000
A call of depth(1000) really does keep a thousand frames alive until the last one returns, and every frame is memory that the engine reserves for it. That is the cost of the style: a loop keeps one frame and a recursion keeps as many as it has levels. The number a program may reach is not part of the language, so a limit is never written into an example; the next section shows what happens when the levels do not stop.
The RangeError at depth
A recursion with no base case, or with one that is never reached, adds frames until the engine refuses to add another. The failure is a RangeError with the message Maximum call stack size exceeded, and the program below catches it so that the run can continue. The depth at which it happens is a property of the engine and the machine, so the program prints the name and the message and never the level.
function withoutBase(n) {
return withoutBase(n + 1) + 1;
}
try {
withoutBase(0);
} catch (error) {
console.log(error.name + ': ' + error.message);
}
function depth(n) {
if (n === 0) {
return 0;
}
return 1 + depth(n - 1);
}
console.log('a small depth still works:', depth(10));
node range.js
RangeError: Maximum call stack size exceeded
a small depth still works: 10
The error is thrown at the moment the stack is full, and the call that throws it is nowhere near the call that started the recursion, which is why the first frames of such a stack trace are all the same function. Catching it and continuing is fine in a demonstration and a bad idea in a program: after a RangeError the stack has unwound, and a function that recurses too deeply is a design problem rather than an accident to be handled. Rewriting the recursion as a loop, or splitting the work into chunks, is the fix.
Recursion over a tree
A tree cannot be walked by a simple loop, because every node may have children of its own. A recursive function fits the shape exactly: the base case is a node with no children, and the step is the node plus the result of the same function on each child. The program counts the nodes and collects their names.
const tree = {
name: 'root',
children: [
{ name: 'a', children: [] },
{ name: 'b', children: [{ name: 'c', children: [] }] },
],
};
function countNodes(nodes) {
return nodes.reduce((total, node) => total + 1 + countNodes(node.children), 0);
}
function collectNames(nodes) {
return nodes.flatMap((node) => [node.name, ...collectNames(node.children)]);
}
console.log('nodes:', countNodes([tree]));
console.log('names:', collectNames([tree]).join(','));
console.log('a leaf:', countNodes([]));
node tree.js
nodes: 4
names: root,a,b,c
a leaf: 0
The root, two children and one grandchild make four nodes, and the names came out in the order a reader of the picture would walk them. The empty array is the base case, and it returns zero because the reduce starts there: a call with no children counts nothing rather than failing. This is the shape a file tree, a comment thread, a menu and the abstract syntax tree of a compiler all have, and it is the reason the recursive walk is worth learning even though a loop can compute a factorial.
Exercises
- Call factorial(0) in base.js. What does it return, and which branch of the function produced that value?
- Print depth(5) with the 1 + removed from the return line. What does the call give now, and why?
- Change the base case of withoutBase in range.js so that it stops at n === 3. Does the program still print the error?
- Add a second child to the node c in tree.js. How many nodes does the count report now, and where does the new name stand in the list?
- Write a recursive function that returns the sum of the numbers stored in a tree of nodes with a value field. Which value does an empty array of nodes contribute?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does a recursive function need before it can stop?
Answer
A base case, and an argument that moves towards it
Without a case that returns without recursing, and an argument that reaches it, the calls never stop.
-
What happens when a recursion never reaches its base case?
Answer
A RangeError about the maximum call stack size
Every unfinished call keeps a frame, and the engine throws when it cannot add another.
-
What does this program print?
function f(n) { return n <= 1 ? 1 : n * f(n - 1); } console.log(f(4));Answer
24
The product is four times three times two times one, with the base case returning one at the bottom.
-
What does this program print?
function f(n) { return f(n + 1); } try { f(0); } catch (error) { console.log(error.name); }Answer
RangeError
There is no base case and the argument moves away from zero, so the stack fills and the error is caught.
-
What does the call stack hold during a recursion?
Answer
One frame for every call that has not returned yet
Each level waits for the level below it, so the frames stay alive until the base case returns.
-
What does this program print?
function sum(n) { return n === 0 ? 0 : n + sum(n - 1); } console.log(sum(4));Answer
10
The base case returns zero and the levels add four, three, two and one on the way back.
-
Why does an example never state the depth at which the RangeError is thrown?
Answer
The limit belongs to the engine and the machine, not to the language
A program that printed the depth would print a different number on another runtime, so only the error name and message are shown.
-
Which data structure makes recursion the natural choice?
Answer
A tree, where every node may hold children of the same shape
A recursive definition of the data matches a recursive function over it, and a loop cannot follow the branches.
-
What does this program print?
function f(n) { if (n === 0) return "done"; return f(n - 1); } console.log(f(3));Answer
done
The return value of the base case travels back through the levels unchanged, since no level computes anything.
-
What is the cost of a recursion compared with a loop?
Answer
One stack frame per level, all alive until the base case returns
The frames are memory, and the limit on their number is what turns a missing base case into a RangeError.
The code on this page was run with Node.js 24.22.1 and linted with ESLint 10.14.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev