Recursion vs Iteration

Anything a loop can compute, a recursive function can compute too, and vice versa — they're equivalent in what they can express. The real difference is never capability. It's what each one costs to run, and that cost comes down to one thing: a recursive call doesn't just repeat work, it also has to remember where it was before making the next call. That memory is the call stack, and it's the entire story below.

The call stack, made concrete

Call factorial(5), and it can't return a value until factorial(4) returns one, which can't return until factorial(3) does, and so on down to the base case. Each of those calls is a real stack frame sitting in memory, still alive, waiting: five frames pushed on the way down, then all five resolving on the way back up as each multiplication finally has both of its operands.

The iterative version never builds this stack at all. A single result variable gets multiplied in place, five times, in a loop — O(n) time either way, but O(n) stack space for recursion versus O(1) for iteration. For factorial(5) that difference is nothing. For factorial of a number that came from user input with no upper bound, it's the difference between a function that always returns and one that can crash the process with a stack overflow.

Why JavaScript can't bail you out here

Some languages eliminate this cost for a specific shape of recursion — a tail call, where the recursive call is the very last thing a function does, with nothing left to compute after it returns. A properly tail-recursive call can reuse its caller's stack frame instead of stacking a new one, turning O(n) stack space back into O(1). factorial as written above isn't a tail call — it still has to multiply by k after the recursive call returns — but even a rewritten, genuinely tail-recursive version wouldn't help in most JavaScript engines. Proper tail calls were specified in ES2015; Safari's JavaScriptCore actually shipped them, but V8 (Chrome, Node.js, Edge) and SpiderMonkey (Firefox) never did. Writing tail-recursive JavaScript today buys you cleaner code, not a smaller stack.

The exponential trap: naive recursive Fibonacci

Factorial's recursion tree is a straight line — one call per level. Fibonacci's naive recursive definition, fib(n) = fib(n-1) + fib(n-2), branches twice per call, and those branches overlap massively: fib(5) and fib(4) both end up computing fib(3) from scratch, independently, with no memory of having done it before. The call counts make the blowup impossible to miss:

fib(10)  ->        177 calls
fib(15)  ->      1,973 calls
fib(30)  ->  2,692,537 calls

That's exponential — O(2ⁿ) — against an iterative version that walks up from fib(0) and fib(1) in a single O(n) loop, tracking only the previous two values. This is precisely why a step-by-step visualizer has to cap naive recursive Fibonacci at a small n: past roughly 30, the call count alone makes it impractical to even render, let alone run.

Memoization: recursion's comeback

The naive version's problem isn't recursion itself — it's redoing identical work. Cache each fib(k) the first time it's computed, and every repeat call becomes a lookup instead of a recomputation:

fib(15) memoized  ->  29 calls  (12 cache hits)
fib(30) memoized  ->  59 calls  (27 cache hits)

59 calls instead of 2.69 million — memoization turns exponential time into linear time, matching the iterative version's O(n). What it does not match is the iterative version's space: the recursive call stack still reaches a depth of n before the first cache hit is even possible, so memoized recursion is O(n) time and O(n) stack space, next to plain iteration's O(n) time and O(1) space. Recursion caught up on speed; it never catches up on stack.

Where recursion is still the right call

None of this makes recursion the wrong default everywhere. Some problems are naturally recursive in shape — trees, nested structures, divide-and-conquer algorithms, backtracking search — and for those, an iterative rewrite doesn't remove the stack, it just relocates it: you end up managing an explicit stack data structure by hand to hold the exact same "where was I" state the call stack would have tracked for free. Walking a binary tree recursively reads as a direct translation of the tree's own recursive definition — a node, plus its left and right subtrees, each handled the same way. The iterative version is the same algorithm wearing a manual stack as a costume, not a fundamentally cheaper one.

Practical guidance

• Simple accumulation over a bounded range? Iterate. There's no O(n) stack to pay for when a loop does the same job in O(1) space.
• Recursive definition with overlapping subproblems (Fibonacci-shaped)? Memoize it, or convert to an iterative bottom-up version if the stack depth genuinely matters — both fix the exponential blowup; only the iterative rewrite also fixes the space.
• Input size is unbounded or attacker-controlled? Prefer iteration, or at minimum know your runtime's stack limit. A recursive function that's perfectly fine at the depths you tested is a denial-of-service bug at a depth you didn't.
• Tree, graph, or backtracking shape? Recursion usually reads closer to the problem statement. Don't iterate it just on principle — measure whether the stack depth is actually a problem for your real input sizes first.

Try it yourself

Recursion vs Iteration Visualizer runs factorial and Fibonacci both ways, step by step — watch the call stack build and unwind frame by frame, toggle memoization on Fibonacci and see the call count and cache hits update live, and compare against the flat variable-tracking of the iterative version. For the complexity classes behind the numbers in this post, see Complexity Visualizer and Big O Calculator. All three run entirely in your browser.