What is recursion?
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem, over and over, until it reaches a version so small it can be answered directly. That smallest version is called the base case; the self-call on a smaller input is the recursive case. Every recursive function is exactly those two parts.
In this lesson you'll learn how to spot a problem that contains smaller copies of itself, trace what actually happens when a function calls itself, and avoid the two bugs that break recursion.
Here's why the idea exists at all. Say you want the total size of a folder on your computer. Easy — add up its files. Except a folder can hold other folders, holding more folders, holding more files… and you have no idea how deep it goes. A plain
for loop assumes you know the shape you're looping over; here you don't. But notice: the size of a folder is its files plus the size of each sub-folder — the problem literally contains smaller copies of itself. So the tool that solves it should call itself too:- base case — a file simply knows its size; answer directly, no further calls
- recursive case — a folder's size = the sum of
sizeOf(child)for everything inside it
Think Russian nesting dolls: open one to find a smaller one, until the tiniest doll stops you — then close them back up in order. Each opened-but-unfinished call waits on the call stack (the runtime's stack of paused function calls) until its smaller call returns.
Quick check
Every recursive function is made of exactly two parts. Which two?
Answer it in the interactive lesson to keep your progress.
How it works, step by step
Let's actually compute a folder's size. The
trip/ folder holds pics/ (two photos, 2 MB and 3 MB) and vids/ (one video, 5 MB). Trace every call:| step | call | what happens |
|---|---|---|
| 1 | sizeOf(trip) | not a file → pauses, asks about its first child |
| 2 | sizeOf(pics) | not a file → pauses, asks about ITS first child |
| 3 | sizeOf(a.jpg) | a file — base case — returns 2 |
| 4 | sizeOf(b.jpg) | base case — returns 3 |
| 5 | sizeOf(pics) resumes | 2 + 3 = 5 → returns 5 |
| 6 | sizeOf(c.mp4) | base case — returns 5 |
| 7 | sizeOf(vids) resumes | returns 5 |
| 8 | sizeOf(trip) resumes | 5 + 5 = 10 → returns 10 |
Two things to notice. Going down, calls only pause — no adding happens yet. Coming back up, each paused call resumes with the answers it was waiting for. The animation below plays exactly this trace — watch the
? marks turn into numbers from the bottom up.Summing a Nested Structure in JavaScript
This section has a step-by-step animation in the interactive lesson.
const trip = {
isFile: false,
children: [
{ isFile: false, children: [
{ isFile: true, size: 2 },
{ isFile: true, size: 3 },
] },
{ isFile: false, children: [{ isFile: true, size: 5 }] },
],
};
function sizeOf(entry) {
if (entry.isFile) return entry.size; // base case
let total = 0;
for (const child of entry.children) {
total += sizeOf(child); // smaller copy of the same job
}
return total;
}
console.log(sizeOf(trip)); // 10Quick check
In the trace, when does the FIRST addition actually happen?
Answer it in the interactive lesson to keep your progress.
Same rhythm, new problem: factorial
The folder was a structure that contained smaller copies of itself. Plain numbers can do it too. Factorial — written
n! — means n × (n−1) × (n−2) × … × 1, and it hides the same shape: factorial(4) is just 4 × factorial(3). Smaller copy, same job.factorial(4)pauses, waiting on4 × factorial(3)factorial(3)pauses, waiting on3 × factorial(2)factorial(2)pauses, waiting on2 × factorial(1)factorial(1)returns1— the base case
Now the stack unwinds:
1 → 2 → 6 → 24. Each call has its own fresh copy of n, so the levels never interfere with each other. (The See it step animates this call stack growing and unwinding, frame by frame.)Factorial by Recursion in JavaScript
function factorial(n) {
// Base case: the simplest input we know directly.
if (n <= 1) return 1;
// Recursive case: smaller problem, then combine.
return n * factorial(n - 1);
}
console.log(factorial(4)); // 24Quick check
During factorial(4), predict the moment the FIRST multiplication actually happens.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- No (or unreachable) base case. The calls never stop, the call stack fills, and the program crashes with a stack overflow. Make sure every path shrinks toward the base case — calling
solve(n)again instead ofsolve(n - 1)is the classic slip. - Redundant recomputation. Some recursions ask the same smaller question many times over (the next section shows the famous example). Left alone, the repeats multiply until the function is unusably slow.
- Deep recursion. Thousands of levels can blow the stack even when the logic is correct. The escape hatch: any recursion can be rewritten as a loop — recursion and iteration are equally powerful. Simple chains (like factorial) become a plain loop; branching recursions use an explicit stack (an ordinary array you push to and pop from) standing in for the call stack, trading stack-overflow risk for heap memory.
One special shape worth knowing by name: when the recursive call is the very last thing the function does — nothing left to compute afterwards — it's called tail recursion. Since no work waits below the call, some languages reuse the current stack frame instead of stacking a new one (tail-call optimization), making the recursion as cheap as a loop. JavaScript engines, however, mostly don't implement it (Safari is the exception) — so in JS, deep recursion overflows whether it's tail-shaped or not, and the loop rewrite is the reliable fix.
Quick check
A recursive case that does NOT shrink the input causes…
Answer it in the interactive lesson to keep your progress.
Take it further — memoize (recursion that remembers)
Meet the famous example of redundant recomputation. The Fibonacci sequence starts
0, 1 and every number after is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, … — so fib(n) = fib(n-1) + fib(n-2), a recursion with two self-calls.That second call is where the trouble starts:
fib(5)asks forfib(4)andfib(3)- but
fib(4)also asks forfib(3)— the same question, answered twice - each repeat branches into its own repeats, and the tree of calls doubles with every level
The fix is to give the recursion a memory — a technique called memoization: store each answer in a cache the first time you compute it, and every later request returns the stored answer instantly. One computation per unique question turns an exponential blow-up into a straight line — and this exact idea grows into dynamic programming, a later lesson. Compute
fib(10).Memoized Fibonacci in JavaScript
function fib(n, memo = {}) {
if (n <= 1) return n;
if (memo[n] !== undefined) return memo[n]; // reuse a cached answer
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
console.log(fib(10)); // 55Quick check
With a memo cache, predict how many times fib(3) is COMPUTED while evaluating fib(10).
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, recursion's cost is the number of calls it makes, and space is how deep the calls stack:
| Recursion | Calls (time) | Stack depth (space) |
|---|---|---|
sizeOf(folder) | O(entries) — one call per file/folder | O(depth) of the folder tree |
factorial(n) | O(n) | O(n) |
naive fib(n) | O(2ⁿ) | O(n) |
memoized fib(n) | O(n) | O(n) |
factorial(n)makesncalls, one at a time →O(n)time,O(n)stack space.- Naive
fib(n)branches into two calls each time, recomputing the same values →O(2ⁿ)time. Memoizing collapses it toO(n). - General rule: time ≈ (number of unique sub-problems) × (work each); space ≈ the deepest the stack ever gets.
Key takeaways:
- Every recursion needs a base case and a recursive case that shrinks toward it.
- Paused calls live on the call stack — that depth is your space cost.
- Overlapping sub-problems? Memoize to turn exponential into linear.
The See it step animates the two classics: the call stack pausing on the way down and computing on the way back up, and memoized fib — watch repeat calls stop dead at the cache instead of re-expanding the whole tree. That engine drives a huge slice of algorithms, each its own lesson later (no need to know them yet): tree and graph traversal (a node is its value plus its recursive children), backtracking (try a choice, then undo it), and divide and conquer (merge/quick sort) plus dynamic programming (recursion + memoization). Next up in order: Binary Trees — a branching structure that recursion fits like a glove.