Before you begin
Why this matters
Recursion is how programs handle data that contains smaller copies of itself, such as folders inside folders, or comments that contain replies to replies. If you can follow one call at a time, you can predict what a recursive function prints and find out why one never stops.
What this helps you reason about
- Spot a function that can never stop calling itself, before you run the code.
- Predict the order of work done before and after a function calls itself.
- Choose a loop when the number of nested calls would grow with the size of the input.
A recursive function solves a problem by calling itself on a smaller version of the same problem. This lesson follows those calls one at a time: how they pile up, how they stop, and what happens on the way back.
Already know this? The short version
- Each call to a recursive function gets its own frame with its own parameters, and the caller waits until that call returns.
- A base case must exist, and every call must move toward it; with number, n <= 0 is safer than n === 0, because negatives and fractions skip 0.
- Code before the recursive call runs on the way down, outermost call first; code after it runs on the way back, innermost call first, and results combine in that same order.
- Node.js does not implement ECMAScript’s proper tail calls, so depth is limited and running out throws RangeError: Maximum call stack size exceeded.
- Use recursion for nested data such as trees, and a loop when the depth would grow with the size of the input.
Words in this lesson (6)
- recursive function
- A function that calls itself. Each call works on a smaller version of the same problem.
- frame
- The record of one function call that has not finished: its parameters and local variables. It is created when the call starts and removed when the call returns.
- call stack
- The frames of all calls that have not finished yet, with the newest on top. A new call adds a frame on top, and a return removes it. Only the newest call runs; each call below it waits for the call it made.
- base case
- The case, an input or a condition such as n === 0, that the function answers without calling itself. Reaching it stops the chain of calls.
- recursive case
- An input the function answers by calling itself on a smaller input and then using that answer.
- stack overflow
- The failure when calls go so deep that the call stack runs out of space. In Node.js it throws RangeError: Maximum call stack size exceeded.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / A call to itself
What happens when a function calls itself?
A recursive function is a function that calls itself. Each of those calls is a separate call: it gets its own parameters and keeps them until it finishes.
countdown(3) prints 3 and calls countdown(2). That call prints 2 and calls countdown(1), and so on. Picture each active call as a box placed on top of the call that made it. Each box is called a frame: it holds one call’s parameters and local variables. The pile of frames is called the call stack. When a call finishes, its frame is removed, and the call underneath it continues.
The stepper shows the same picture. Its frame list has one frame for each active call, with the newest call at the top.
function countdown(n: number): void {
if (n === 0) {
console.log("liftoff");
return;
}
console.log(n);
countdown(n - 1);
}Every call to countdown is a separate call with its own n.
Precisely: the stack is a model
The language promises that each call has its own bindings and returns to its caller. The call stack is a model of that promise. The JavaScript engine (the program that runs JavaScript, V8 in Node.js) chooses how to represent it. When it optimizes code, it may keep values in the processor’s registers instead of a frame, or remove calls.
Experiment
Follow a countdown to its base case
Each call to countdown is a separate call with its own parameter. A call does not finish until the call it made has finished. So countdown(3) waits for countdown(2), countdown(2) waits for countdown(1), and countdown(1) waits for countdown(0).
Why it matters You can follow any recursive function the same way: one call at a time, each with its own values.
Predict how many countdown calls are active when liftoff prints. Then delete the base case (the whole if block) and run again.
function countdown(n: number): void {
if (n === 0) {
console.log("liftoff");
return;
}
console.log(n);
countdown(n - 1);
}
countdown(3);
What to look for
Watch the frame list: each call to countdown adds one frame, with its own n. Each frame also lists countdown itself, shown as function countdown(n): the name countdown is a variable that holds the function, and the later experiments show their functions the same way. Step sometimes stops on the same line two or three times; that is normal for this debugger. Without the base case, n goes below 0 and new frames keep appearing. The runner then ends the run with a message that begins "Stopped after". You will not see RangeError: the runner stops long before the real stack runs out.
Expected output
3
2
1
liftoff02 / Base case
What makes the recursion stop?
The base case is the case, an input or a condition, that the function answers directly, without calling itself. Every other input is the recursive case: the function calls itself with a smaller input. Without a base case, every call makes another call, and the program cannot finish on its own.
The calls must also reach the base case. countdown(n - 1) makes n smaller by one each time, so any positive whole number reaches 0. But with the test n === 0, countdown(-1) calls countdown(-2), then countdown(-3), and never reaches 0. The test n <= 0 makes every starting number stop.
function countdown(n: number): void {
if (n <= 0) {
console.log("liftoff"); // base case: answer directly
return;
}
console.log(n);
countdown(n - 1); // recursive case: a smaller input
}Check two things: a base case exists, and every call gets closer to it.
Coming from React: A component that renders its own replies is recursive too: each level is a separate call with its own props, and a comment with no replies is the base case.
Precisely: number includes fractions
TypeScript’s number type also allows 2.5. With n === 0, countdown(2.5) would pass 1.5, 0.5, then -0.5 and never stop. With n <= 0 it stops at -0.5. The type number does not promise a whole number.
03 / The way back
What happens after the recursive call returns?
A recursive call pauses the current call; it does not end the current call. When visit(2) finishes, visit(3) continues from the line after its recursive call.
So work written before the recursive call happens on the way down, while calls are still being made: visit(3) first, then visit(2), then visit(1). Work written after it happens on the way back, while the calls are returning and each paused call continues: visit(1) first, then visit(2), then visit(3).
function visit(level: number): void {
if (level === 0) return;
console.log("enter " + level);
visit(level - 1);
console.log("leave " + level);
}Code before the recursive call runs on the way down; code after it runs on the way back.
Experiment
Watch work happen on the way back
Each visit call prints its enter line, then makes its recursive call and pauses there. It prints its leave line only after the call it made has returned. So the newest call, visit(1), is the first to print leave.
Why it matters Where you put work relative to the recursive call decides its order. This is how a recursive function can reverse a sequence without a separate reverse step.
Predict the order of all six lines before running. Then move the leave line above the recursive call and predict again.
function visit(level: number): void {
if (level === 0) return;
console.log("enter " + level);
visit(level - 1);
console.log("leave " + level);
}
visit(3);
What to look for
Watch the output panel and the frame list together. The enter lines appear while frames are added: visit(3), then visit(2), then visit(1). The leave lines appear as frames are removed: leave 1 first, then leave 2, then leave 3. After the edit, each leave line comes right after its enter line, while calls are still being made: enter 3, leave 3, enter 2, leave 2, enter 1, leave 1.
Expected output
enter 3
enter 2
enter 1
leave 1
leave 2
leave 304 / Combining results
How do the answers come together?
Most recursive functions return a value. Each call asks a smaller version of the question and uses the answer. values.slice(1) is a new array with every element except the first, so total([4, 2, 7]) asks for total([2, 7]), which asks for total([7]), which asks for total([]). The empty list is the base case: its total is 0.
The answers come back in reverse order: 0, then 7, then 9, then 13. Each addition waits until the call it depends on has returned.
function total(values: number[]): number {
if (values.length === 0) return 0;
const rest = total(values.slice(1));
return values[0] + rest;
}Assume the smaller call returns the right answer, then use it.
Coming from Python: Like Python’s values[1:], values.slice(1) copies the remaining elements into a new array.
Precisely: slice copies
values.slice(1) creates a new array each time, copying the remaining elements. For a list of n numbers that copies about n²/2 elements in total. Passing a start index instead of slicing avoids the copies.
Experiment
Combine results from smaller calls
Each call answers a smaller version of the question and then uses that answer. The base case answers the smallest version directly. The results are combined on the way back, starting from the base case.
Why it matters You do not need to follow every call to check a recursive function. Check that the base case is right. Then check that each call combines a correct smaller answer correctly.
Predict what each call returns before running. Then change the 2 in the list to 5 and predict the new total.
function total(values: number[]): number {
if (values.length === 0) return 0;
const rest = total(values.slice(1));
return values[0] + rest;
}
console.log(total([4, 2, 7]));
What to look for
When the base case returns, select each earlier frame in turn. Each frame keeps its own values and receives the smaller call’s result as rest. After the edit, the run prints 16.
Expected output
1305 / Depth
How deep can it go, and when is a loop better?
Each frame takes some memory, and the space for frames is limited. A recursion that goes many thousands of calls deep can run out. In Node.js, that throws RangeError: Maximum call stack size exceeded.
When the depth grows with the size of the input, such as one call per list element, a loop is usually the safer choice. Recursion fits best when the data itself is nested, like folders inside folders, where the depth stays small.
function total(values: number[]): number {
let sum = 0;
for (const value of values) sum += value;
return sum;
}Use recursion when the problem is nested; prefer a loop when depth would grow with the input.
Coming from Python: Python stops at a fixed count of about 1,000 calls with RecursionError; Node.js stops when its stack memory runs out, usually after about ten thousand simple calls, with RangeError.
Precisely: the limit is not fixed
The maximum depth depends on the engine, its settings, and how much each call stores. ECMAScript specifies proper tail calls: a call made as the very last step of a function may reuse that function’s frame instead of adding one. V8, the JavaScript engine inside Node.js, does not implement them, so every call adds a frame.
06 / Try it
Can you follow a fresh example?
Predict the output before revealing the answer. Ask where the print sits relative to the recursive call.
function show(n: number): void {
if (n === 0) return;
show(n - 1);
console.log(n);
}
show(3);
What does this print, and why in that order?
Reveal the reasoning
1, then 2, then 3. show(3) calls show(2), which calls show(1), which calls show(0). show(0) returns immediately. Then show(1) continues and prints 1, show(2) prints 2, and show(3) prints 3. The print comes after the recursive call, so it runs on the way back.
Practice tickets
- REC-101 · Fix the parcel check number → Free
- REC-102 · Count every nested folder → Sign in · Pro
- REC-103 · Show the reporting chain → Sign in · Pro