What recursion is
You want the total size of a folder. 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. The structure is self-similar — a folder is files plus more folders — so the tool should be self-similar too.Recursion is a function that solves a big problem by calling itself on a smaller piece, until the piece is trivial. Every recursion needs exactly two parts:
- a base case — the smallest input, answered directly with no further calls (an empty folder totals
0) - a recursive case — break the problem down and call yourself on the smaller parts (a folder = its files plus the total of each sub-folder)
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 paused call waits on the call stack until its sub-call returns.
Quick check
Where do paused recursive calls wait?
Answer it in the interactive lesson to keep your progress.
How it works, step by step
Check the base case first and return immediately if it's met; otherwise do a little work and call yourself on a smaller input. The classic warm-up is
factorial(n) = n * factorial(n-1), base case factorial(1) = 1:factorial(4)waits on4 * factorial(3)factorial(3)waits on3 * factorial(2)factorial(2)waits 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 the locals, so the levels never clobber each other. In the animation, watch the call stack grow downward as each call pauses to wait on a smaller one — then watch it unwind in reverse order, each level multiplying the answer coming back up. Before each frame, predict: is the next move a new call (stack grows) or a return (stack shrinks)?This section has a step-by-step animation in the interactive lesson.
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 you get a stack overflow. Make sure every path shrinks toward the base case.
- Redundant recomputation. Naive
fib(n) = fib(n-1) + fib(n-2)recomputes the same values an exponential number of times. Memoize — cache each answer the first time. In the animation below, watch the call tree: without the cache the same sub-values light up again and again; with it, repeat calls stop instantly at the cache instead of re-expanding the whole subtree. - Deep recursion. Thousands of levels can blow the stack even when correct; some recursions are better rewritten as loops.
This section has a step-by-step animation in the interactive lesson.
Quick check
A recursive case that does NOT shrink the input causes…
Answer it in the interactive lesson to keep your progress.
What is the Fibonacci sequence?
The Fibonacci sequence is a series of numbers where each number is the sum of the two before it. It starts with 0 and 1: The sequence unfolds: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
You see it everywhere in nature — spiral shells, flower petals, even how rabbits breed. The pattern is simple, but computing it naively is expensive:
fib(5) = fib(4) + fib(3)fib(4) = fib(3) + fib(2)- Notice:
fib(3)appears twice, and it callsfib(2)again redundantly
The naive recursion branches exponentially, recalculating
fib(3) and smaller values dozens of times. That's O(2^n) — catastrophically slow for fib(50) or beyond.Quick check
Why does naive Fibonacci recursion recompute values?
Answer it in the interactive lesson to keep your progress.
Take it further — memoize (recursion that remembers)
The fix is to cache results: store each answer the first time, and reuse it after. Instead of recalculating
fib(3) a dozen times, solve it once and store the result. That turns O(2ⁿ) into O(n) — and it's the exact idea behind dynamic programming. Compute fib(10):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) |
|---|---|---|
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.
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.