Understanding Recursion With Practical Examples
How recursion actually works, when it beats a loop, how the call stack behaves, and the mistakes that turn a simple function into a crash.
By Velloreth
What recursion actually is
Recursion is a function that calls itself on a smaller version of the same problem. That is the whole idea, and it is worth stating plainly because the word makes it sound harder than it is.
A recursive function needs exactly two parts:
- A base case that returns a value without recursing. This is what stops the process.
- A recursive case that calls the function again on input that is strictly closer to the base case.
If either part is missing or wrong, the function either crashes or never terminates. There is no third outcome.
The reason recursion is worth learning is not that it is clever. It is that some data is genuinely recursive — a directory tree, a JSON document, an arithmetic expression — and a recursive function describes those shapes far more directly than a loop does.
The call stack is the thing to understand
Every time a function is called, the runtime pushes a frame onto the call stack. That frame holds the arguments, the local variables, and the address to return to. When the function returns, the frame is popped.
Recursion is therefore not free. A recursive call that is 1,000 levels deep has 1,000 frames alive at once. This is the single most important practical fact about recursion, because it explains the failure mode you will actually hit.
| Language | Typical default limit | Error on overflow |
|---|---|---|
| JavaScript (V8) | ~10,000–15,000 frames | RangeError: Maximum call stack size exceeded |
| Python | 1,000 frames | RecursionError: maximum recursion depth exceeded |
| Java | ~10,000–20,000 frames | StackOverflowError |
| Go | Grows dynamically | Eventually fatal error: stack overflow |
Those numbers are approximate and depend on frame size, but the order of magnitude is what matters. A recursion that is fine on a 100-element array will crash on a 100,000-element one.
A first example: factorial
The textbook example is factorial, and it is worth writing once because it shows the two parts clearly.
function factorial(n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
factorial(5); // 120
Trace it and you can see the stack build up: factorial(5) waits on factorial(4), which waits on factorial(3), and so on down to factorial(1), which returns immediately. Then the multiplications unwind back up the stack.
The base case is n <= 1 rather than n === 1 on purpose. That single change makes the function return 1 for 0 and for negative numbers instead of recursing forever. Defensive base cases are cheap insurance.
The two ways recursion goes wrong
Almost every recursion bug is one of two things.
No base case, or an unreachable one. The function recurses until the stack overflows. This is the error you will see most often, and the fix is to check that the base case is actually reachable from every input.
A recursive case that does not shrink the problem. This is subtler. Consider a function that calls itself with the same argument, or with an argument that oscillates between two values. It has a base case, but it never reaches it. The symptom is identical — a stack overflow — but the cause is different, so check both.
A useful habit is to state the invariant out loud: each call receives input strictly closer to the base case than the last. If you cannot state that, the function is not correct yet.
Recursion versus iteration
Any recursive function can be rewritten as a loop, and any loop can be rewritten as recursion. They are equally powerful. The choice is about clarity and memory.
| Recursion | Iteration | |
|---|---|---|
| State lives in | The call stack | Local variables |
| Memory growth | One frame per level | Constant, usually |
| Depth limit | Bounded by the stack | Bounded by available memory |
| Reads best for | Trees, graphs, divide and conquer | Flat sequences, counters, accumulators |
| Typical failure | Stack overflow | Off-by-one, infinite loop |
The practical rule: if the data is recursive, write it recursively. If the data is a flat list, write a loop. Fighting that instinct produces code that is harder to read for no benefit.
Converting recursion to iteration
When depth is the problem, you convert. The mechanical approach is to replace the call stack with an explicit one.
// Recursive
function sumTree(node) {
if (!node) return 0;
return node.value + sumTree(node.left) + sumTree(node.right);
}
// Iterative, with an explicit stack
function sumTreeIterative(root) {
let total = 0;
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
if (!node) continue;
total += node.value;
stack.push(node.left, node.right);
}
return total;
}
The iterative version uses heap memory instead of stack memory, so it is bounded by how much RAM you have rather than by the call stack. For a tree a million nodes deep, that is the difference between working and crashing.
Note that the two versions are not always equally readable. The recursive one states the intent in three lines; the iterative one needs a loop and a manual stack. That trade-off is the real decision.
Tail calls and why they are not a safety net
A call is in tail position when it is the last thing the function does, with no work left afterwards. In the factorial above, the recursive call is not in tail position, because the multiplication still has to happen after it returns.
Rewrite it with an accumulator and the call moves into tail position:
function factorialTail(n, acc = 1) {
if (n <= 1) return acc;
return factorialTail(n - 1, n * acc); // tail call
}
Some runtimes detect this and reuse the current frame instead of pushing a new one, which turns the recursion into a loop and removes the depth limit entirely. Scheme requires it. JavaScript’s strict mode once specified it but no mainstream engine implements it. Python does not do it. So treat tail-call optimisation as a bonus where it exists, never as a guarantee you rely on.
Where recursion is the right tool
Recursion earns its place in a specific set of problems:
- Tree traversal — walking a DOM, a file system, or an abstract syntax tree.
- Divide and conquer — merge sort, quicksort, and binary search all split the input and recurse.
- Backtracking — solving mazes, generating permutations, and constraint problems.
- Parsing nested structures — JSON, HTML, and arithmetic expressions are recursive by nature.
- Graph traversal — depth-first search is naturally recursive.
In each case the shape of the code mirrors the shape of the data, which is exactly what you want. If you are working through debugging strategies that work, you will notice that recursive bugs are usually found by tracing the depth rather than the values.
Memoisation: making recursion fast
Naive recursion can be exponentially slow. The classic example is computing Fibonacci numbers, where fib(n) calls fib(n-1) and fib(n-2), and those calls overlap enormously.
function fib(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const result = fib(n - 1, memo) + fib(n - 2, memo);
memo.set(n, result);
return result;
}
Caching the results turns an exponential algorithm into a linear one. This technique is called memoisation, and it is the foundation of dynamic programming. The recursive structure stays readable while the cost collapses.
Practical habits that prevent recursion bugs
A few habits catch most recursion problems before they reach production:
- Write the base case first. Before the recursive case, before anything else.
- Assert the shrink. Confirm each call moves toward the base case.
- Test the boundaries. Empty input, one element, and the deepest realistic input.
- Know your depth limit. If the input can exceed a few thousand levels, plan the iterative version.
- Add a depth guard in development. A counter that throws at a sane limit turns a mysterious crash into a clear error.
That last one is worth the two lines it costs. A depth guard tells you which input was too deep, which a stack overflow never does.
How to practise recursion
Recursion is one of those skills that clicks through repetition rather than reading. The fastest route is to solve the same small problem three ways: recursively, iteratively, and with memoisation. Comparing the three versions teaches the trade-offs far better than any explanation.
Start with problems you can already solve in a loop — reversing a string, summing a list, finding the maximum — and rewrite them recursively. Then move to problems that are awkward without recursion: flattening a nested array, walking a tree, generating permutations. The second group is where the technique stops feeling like a trick and starts feeling like the obvious choice.
If you are still building fundamentals, learning programming without tutorial hell and a junior developer’s guide to reading code both pair well with this kind of deliberate practice.
Summary
Recursion is a function calling itself on a smaller input, with a base case to stop and a recursive case that provably shrinks the problem. Its cost is stack frames, which is why depth is the limit that matters. It is the clearest way to express tree, graph, and divide-and-conquer algorithms, and it converts mechanically to a loop with an explicit stack when depth becomes a problem. Learn the base case first, keep the shrink honest, and know your runtime’s depth limit — that is most of what there is to know.