Recursion vs Iteration
Recursion when the problem is defined recursively, which trees, backtracking and divide and conquer all are. Iteration when the depth could be large, or when the loop is genuinely simpler to read, which for linear scans it usually is.
Anything written recursively can be written iteratively and the reverse, so this is a question about clarity and stack depth rather than capability. The useful framing is that recursion uses the call stack to hold state you would otherwise have to manage yourself. When that state is a path through a tree, letting the runtime hold it is a large simplification. When it is a single counter, it is overhead.
Side by side
| Dimension | Recursion | Iteration |
|---|---|---|
| State lives | On the call stack | In variables you declare |
| Depth limit | Yes, the stack overflows | None |
| Overhead per step | A stack frame | Effectively none |
| Reads well for | Trees, backtracking, divide and conquer | Linear scans, accumulation |
| Java tail calls | Not optimised, depth still counts | Not applicable |
| Converting away | Replace the call stack with an explicit stack | Usually straightforward |
When to pick each
Recursion
- Tree and graph traversal, where the recursion mirrors the structure.
- Backtracking, where the undo step is simply returning from a call.
- Divide and conquer, where the recursive case is the definition of the algorithm.
Iteration
- Depth could reach tens of thousands, which overflows the default JVM stack.
- The recursion is linear and carries one accumulator, such as a factorial or a list sum, where the loop is plainly simpler.
- The constant factor matters in a hot path.
Assuming a tail-recursive function is safe in Java because it would be optimised elsewhere. The JVM does not eliminate tail calls, so a tail-recursive walk down a million-node linked list overflows exactly as a non-tail-recursive one would. Scala and Kotlin can optimise it with explicit support; plain Java cannot.
Questions people ask
How deep can Java recursion go?
Typically somewhere around ten thousand frames on the default stack, though it depends on frame size and the -Xss setting. Treat any recursion whose depth scales with input size as a risk once the input reaches thousands.
Is recursion slower?
Per step, slightly, because each call sets up a frame. It is rarely the bottleneck, and choosing an iterative version for speed alone is usually a premature optimisation. Choosing it to avoid a stack overflow is not.
How do I convert recursion to iteration?
Replace the call stack with an explicit stack holding whatever the recursive call would have carried. For single recursion, such as walking a list, a plain loop is enough. For tree recursion you need the stack, which is exactly what iterative tree traversals do.