What is recursion?
Recursion is a function that calls itself on a smaller version of the same problem, until it hits a
base case simple enough to answer directly. Every recursive solution needs both pieces — a base
case that stops the recursion, and a recursive case that makes real progress toward it — or it
never terminates.
- Base case
- The smallest version of the problem, simple enough to answer directly without recursing further
- Recursive case
- The step that calls the function again on a smaller version of the same problem
- Call stack
- The pending calls, each waiting for its recursive call to return before it can finish its own work
Why recursion at all?
Picture a set of Russian nesting dolls. To open the whole thing you open the outermost doll, which reveals a smaller version of the exact same problem: another doll to open. You keep going until you hit the solid smallest doll — the base case — that can't be opened any further.
Every call in between is stuck waiting. It can't do anything with what's inside until the doll it just opened is fully dealt with. That's the call stack: a pile of paused work, each frame holding onto its own piece, waiting for the frame below it to finish.
Each call waits for the one below it to return before it can finish its own work.
What shapes does recursion take?
The call stack looks the same underneath every time — frames pushed, then popped in reverse order. What changes is how many recursive calls each frame makes, and what it does with the answer once it gets one back.
Linear recursion
One call makes exactly one recursive call — factorial and reversing a linked list both work this way. The stack grows in a straight line down to the base case, then unwinds the same way back up.
One call in, one call out — the stack never branches.
Tree recursion
One call makes two (or more) recursive calls — walking a binary tree's depth calls itself once for the left child and once for the right. The stack still grows and shrinks one call at a time; it just does the whole thing twice, once per branch.
The left branch fully resolves before the right branch ever starts.
Divide and conquer
One call makes one recursive call on roughly half the problem, then combines that single answer into its own — computing x n by squaring x n/2 is the classic example. Halving means the stack only ever grows to O(log n) deep.
Halving the exponent every call keeps the stack shallow — O(log n), not O(n).
Every recursive call needs two pieces
Skip the base case and the calls never stop, until the call stack overflows. Skip real progress in the recursive case — passing along the same input instead of a smaller one — and you get the same result: it never reaches a case that can stop it.
Base case
The smallest input the function can answer directly, with no further recursion. It's checked first, before any recursive call is made — that check is what guarantees the recursion eventually stops.
function factorial(n: number): number {
if (n <= 1) {
return 1; // base case — answer it directly, no more recursion
}
return n * factorial(n - 1); // recursive case
}
Recursive case
Calls the function again on a smaller version of the same problem — one element removed, one index closer to the end, half the range. "Smaller" is what guarantees progress: eventually the input has to shrink all the way down to the base case.
function sum(arr: number[]): number {
if (arr.length === 0) {
return 0; // base case — nothing left to add
}
return arr[0] + sum(arr.slice(1)); // recursive case — one element smaller
}
Where it works — and where it breaks
Recursion is a great fit when the problem's own definition is already recursive. It's a poor fit when the input is just a long, flat pass — there the call stack costs you something iteration never would.
Shines on trees and divide-and-conquer
A tree is defined recursively — a node with subtrees that are themselves trees — so recursive code reads almost exactly like that definition. The recursion depth only ever reaches the tree's height, which for a balanced tree is a comfortable O(log n).
Breaks on a long, flat pass
Recursing once per element of a 100,000-item array pushes 100,000 frames onto the call stack — each
one holding its own place in line, none of them able to free their memory until the very last one
returns. Most runtimes give up long before that: Maximum call stack size exceeded.