Is recursion slower than iteration?
Is recursion slower than iteration? Usually by a small constant, sometimes not at all, and occasionally catastrophically, when the recursion recomputes subproblems or exhausts the stack. The real cost is not the function call; it is the shape of the work. Here is how to tell the three cases apart.
Recursion is slower than iteration by a small constant factor in most languages, because a call pushes a frame and a loop increments a counter. That difference is real, measurable, and rarely the thing that matters. When recursion is dramatically slower, the cause is never the call itself: it is that the recursive formulation does exponentially more work, or that it runs out of stack. Distinguishing those cases is the whole skill.
The question usually arrives after a specific experience: someone wrote a recursive Fibonacci, watched it take seconds for n equals 40, rewrote it as a loop, and concluded that recursion is slow. The loop was faster by a factor of about a hundred million, which no function-call overhead could explain. The recursive version was doing a different, much larger computation. Blaming the calls is like blaming the postage for the cost of mailing every page of a book separately.
What does a function call actually cost?
A call pushes a return address and the callee's frame onto the stack, moves arguments into place, jumps, and later pops and returns. On a modern processor that is a handful of instructions and a few nanoseconds, comparable to a loop iteration with a couple of extra memory writes. For a recursion of depth n with constant work per level, the total is n calls: linear, the same order as the loop, with a constant factor typically between one and three depending on the language and how much the compiler optimises.
That constant matters in a tight inner loop and nowhere else. If a function is called ten million times per second, the frame traffic shows up in a profile. If it is called a thousand times to traverse a tree, the difference is unmeasurable against everything else the program does. Managed runtimes add a little: Python calls are noticeably heavier than C calls, and a recursive Python traversal of a large list will lose to its loop by a wider margin than the equivalent in Rust. Still a constant, still not the story.
When is recursion exponentially slower?
When the recursion tree contains the same subproblem many times. Naive Fibonacci calls fib(n minus 1) and fib(n minus 2); the second of those is recomputed inside the first, and the tree has on the order of the golden ratio to the power n nodes, so fib(40) makes over three hundred million calls to compute a number that fits in a 32-bit integer. The loop computes each value once: forty additions. The ratio is not overhead; it is the difference between exponential and linear work.
This is the case people mean when they say recursion is slow, and the fix is not to abandon recursion but to stop repeating work. Memoisation stores each subproblem's answer on first computation and returns it on every later request, which collapses the exponential tree into the linear chain the loop was already walking. The memoisation versus tabulation deep-dive compares the two ways of doing this, top-down with a cache and bottom-up with a table, and the counting argument that shows both are O(n) for Fibonacci. The point for this essay: once subproblems are shared, recursive and iterative solutions do the same amount of work, and the remaining difference is the constant from the previous section.
When does recursion fail entirely?
When the depth exceeds the stack. Each frame consumes stack memory, and the stack is small by design: a megabyte or so in many environments, and Python caps recursion at around a thousand frames by default. A recursive function that walks a linked list of a hundred thousand nodes, or performs depth-first search on a long path graph, will not be slow; it will crash. Iteration with an explicit stack uses heap memory instead, which is limited by the machine rather than by a runtime constant, and this is the strongest practical argument for converting recursion to iteration in production code.
Two mitigations exist. Tail-call elimination lets a compiler turn a recursive call in tail position into a jump, reusing the frame, so depth costs nothing; some languages guarantee it, most do not, and relying on it in a language that does not is a bug waiting for a large input. The other is the manual conversion: replace the call stack with your own stack of pending work, which is exactly what the iterative tree traversal deep-dive does for in-order, pre-order, and post-order walks. The code is longer and the reasoning is harder, which is why the recursive version is worth writing first even when the iterative one is what ships.
Which form should you write?
Write the one whose correctness you can argue, then convert only if measurement or depth forces it. Recursion is the natural expression of any problem defined in terms of smaller instances of itself: trees, divide and conquer, backtracking, grammar parsing. For those, the recursive version mirrors the inductive proof that it works, an argument developed in recursion as induction, and the iterative version obscures it. Loops are the natural expression of sequential accumulation, and a recursive sum-of-a-list is a worse program than its loop in every respect, including readability.
| Situation | Recursive cost | Iterative cost | Verdict |
|---|---|---|---|
| Sequential accumulation (sum, max, count) | n frames, stack risk | n iterations, no stack | Loop |
| Tree of depth log n (balanced BST, merge sort) | log n frames, negligible | Manual stack, more code | Recursion |
| Overlapping subproblems (Fibonacci, DP) | Exponential unless memoised | Linear with a table | Either, once shared |
| Deep linear structure (long list, path graph) | n frames, overflows | Explicit stack on the heap | Loop or explicit stack |
One more practical note on measurement. When you benchmark the two forms, benchmark the same algorithm in both shapes, not naive recursion against a memoised loop; that comparison measures the memoisation, not the recursion. A fair test is merge sort written recursively against merge sort with an explicit stack, or a memoised recursive Fibonacci against its table. Run both at a size where the work dominates the call overhead, and the gap will usually be under a factor of two.
The table has a pattern: depth is what decides. Logarithmic depth makes recursion free and clear. Linear depth makes it dangerous. Exponential breadth makes it wrong until memoised, at which point the depth rule takes over again. Ask "how deep, and how much repeated work" and the answer to "which form" follows.
Frequently asked questions
Does the compiler convert recursion to loops automatically?
Only for tail calls, and only in languages or compilers that implement tail-call elimination. C compilers do it at higher optimisation levels when the call is truly in tail position; Python and Java do not. A recursive call followed by any further work, such as adding one to the result, is not a tail call and cannot be eliminated.
Is memoised recursion as fast as a bottom-up loop?
Same asymptotic cost, and the loop is usually faster by a constant because it avoids cache lookups and frames. The memoised version wins when only a sparse subset of subproblems is needed, since the loop computes all of them. For dense problems like Fibonacci, prefer the table.
How deep can recursion safely go?
Assume a few thousand frames in interpreted languages and tens of thousands in compiled ones with default stack sizes. Balanced trees and divide-and-conquer stay far under that. Anything with depth proportional to input size needs an explicit stack or a guaranteed tail call.
To see the conversion done carefully on the structure where it matters most, read iterative BST traversal, then compare it with the recursive walk in the trees module.