vault

Recursion vs Iteration

22 min read

Recursion vs Iteration

Recursion and iteration are two ways to express the same computation. Recursion expresses “do X, then solve a smaller version of the same problem”; iteration expresses “do X repeatedly until done”. The classical theorem says every recursive algorithm can be made iterative — but the conversion may require an explicit stack to simulate the call stack the runtime was managing for you. The choice between the two is about clarity vs. constraints: recursion is clearer for tree-shaped problems (DFS, divide-and-conquer); iteration is necessary when the language doesn’t optimize tail calls (Python, Java) and recursion depth would blow the call stack.

1. Intuition — Two Ways to Climb a Staircase

Imagine climbing a staircase of n steps. Iteration says: “I’ll take a step. Am I at the top? No — take another step. Repeat until done.” A loop. Recursion says: “Climbing n steps is one step plus climbing n − 1 steps. Climbing 0 steps is trivial.” Each recursive call delegates the rest of the work to a fresh sub-call, and the runtime stacks those calls — n frames deep when you start, unwinding as each sub-call completes.

Both compute the same answer. But:

  • The iterative version uses a single loop variable and a small constant amount of memory.
  • The recursive version uses n stack frames, one per level of recursion.

Why prefer recursion? Because for tree-shaped problems (a binary tree has two children — climbing it isn’t a linear sequence), the recursive structure is the natural one. Two recursive calls neatly reflect two children. Doing it iteratively requires an explicit stack data structure to simulate what the call stack was doing implicitly.

Why prefer iteration? Because every recursive call eats stack frames, and stacks are bounded. In Python (default limit ~1000 Python calls), on the JVM (default 1 MB thread stack on 64-bit HotSpot), in embedded systems (kilobytes), exceeding the limit crashes your program with a RecursionError or stack overflow. Iteration uses heap-allocated data structures (which can grow much larger) and avoids that ceiling.

2. The Stack Frame — What Each Recursive Call Costs

When a function calls itself, the language runtime allocates a stack frame containing:

  • The function’s local variables.
  • The arguments passed to this call.
  • The return address (where to jump back to when the call finishes).
  • A few bookkeeping bytes (frame pointer, etc.).

In CPython the per-call cost is implementation-defined and has shrunk substantially over time. Through CPython 3.10 every call heap-allocated a full frame object on the order of several hundred bytes; since 3.11 the interpreter uses a leaner internal _PyInterpreterFrame allocated on a contiguous data stack rather than a per-frame heap object (PEP 659; CPython interpreter internals doc), which is one reason 3.11+ function calls are faster and lighter. The exact byte count is not part of the language contract — treat it as “low hundreds of bytes, version-dependent.” What matters for this note is the count: the default Python recursion limit is 1000 Python-call frames, and exceeding it raises RecursionError.

In compiled languages (C, C++, Rust), each stack frame can be as small as a few dozen bytes (just whatever the function uses). HotSpot’s default thread stack on 64-bit Linux/macOS/Solaris is 1024 KB (1 MB), configurable with -Xss / -XX:ThreadStackSize (per the java tool reference for JDK 17; the 32-bit VM historically defaulted to 320 KB); exceeding it raises StackOverflowError.

The takeaway: recursion depth costs memory linearly. A recursion that goes n deep uses Θ(n) stack space on top of whatever the algorithm itself allocates. This is what we mean by recursion’s “space complexity contribution.”

3. Tiny Worked Example — Factorial Two Ways

3.1 Recursive

def factorial_rec(n):
    if n <= 1:
        return 1
    return n * factorial_rec(n - 1)

For n = 5, the call stack grows to depth 5:

factorial_rec(5)
  → factorial_rec(4)
    → factorial_rec(3)
      → factorial_rec(2)
        → factorial_rec(1) returns 1
      returns 2 * 1 = 2
    returns 3 * 2 = 6
  returns 4 * 6 = 24
returns 5 * 24 = 120

Each level holds n in its stack frame, waiting on the result. Time Θ(n), space Θ(n) (for the call stack).

3.2 Iterative

def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Same answer in Θ(n) time, but now Θ(1) space — just the loop variable and the running product. No stack growth.

For factorials, the iterative version is strictly better in resource usage and only marginally less readable. For tree traversals, the recursive version is dramatically more readable, and the resource hit is rarely a problem until the tree gets very deep.

4. Tail Calls and Tail-Call Optimization

A tail call is a recursive call that is the last action of the function — its return value is returned directly, with no post-processing. The hallmark: return f(...) rather than return x + f(...) or return f(...) + 1.

def sum_tail(n, acc=0):
    if n == 0:
        return acc
    return sum_tail(n - 1, acc + n)   # tail call: result is returned directly
 
def sum_not_tail(n):
    if n == 0:
        return 0
    return n + sum_not_tail(n - 1)    # NOT tail: post-processing (the addition)

The crucial insight: in a tail call, the calling frame’s locals are no longer needed — there is nothing left to do after the call returns except return its value. So a clever compiler can reuse the caller’s stack frame for the callee, turning the recursion into a loop in disguise. This is tail-call optimization (TCO), and it makes tail-recursive programs run in O(1) stack space.

4.1 Languages with TCO

  • Scheme — guaranteed by the language standard (R5RS, R6RS, R7RS). Scheme programs rely on TCO; idiomatic Scheme uses recursion where other languages use loops.
  • OCaml, Haskell, Erlang, Standard ML — guaranteed.
  • Lua — guaranteed (since 5.1, return f(...) form).
  • Some C/C++ compilers — opportunistically with -O2. Not guaranteed by the language standard.
  • Lua — guaranteed. The Lua 5.4 manual states explicitly: “In a tail call, the called function reuses the stack entry of the calling function. Therefore, there is no limit on the number of nested tail calls that a program can execute” (Lua 5.4 Reference Manual §3.4.10). The qualifying form is return functioncall with a single call as its sole argument, outside the scope of any to-be-closed variable.
  • JavaScript — “proper tail calls” (PTC) are mandated by the ES2015 (ES6) specification, but as of 2026 the only mainstream engine to ship them is Apple’s JavaScriptCore (Safari). V8 (Chrome, Node.js) has not implemented them — the V8 team began an implementation, hit edge cases producing incorrect behavior, viewed the optimization as roughly performance-neutral, and ultimately declined to ship it, partly over the loss of stack-trace fidelity (Chrome Platform Status: “Tail call elimination (ES6)”). So in Node.js a tail-recursive function still grows the stack and throws RangeError: Maximum call stack size exceeded. Treat JS TCO as absent unless you are specifically targeting Safari.

4.2 Languages WITHOUT TCO

  • Python — Guido van Rossum has explicitly rejected adding TCO (blog post 2009: “Tail Recursion Elimination”; see also PEP 666 — joke proposal “Reject foolish indentation” which captures the philosophy: tracebacks are valuable, TCO sacrifices them). Python deliberately does not optimize tail calls. Recursion in Python is always limited by sys.getrecursionlimit() (default 1000).
  • Java — JVM specification doesn’t require TCO, and HotSpot doesn’t perform it on the bytecode level. Java’s StackOverflowError is a real concern for deep recursion.
  • Most mainstream imperative languages.

Python’s recursion limit is a Python-function-call-count limit, not a byte limit: sys.getrecursionlimit() returns 1000 by default, and you raise it with sys.setrecursionlimit(N). A subtlety worth knowing, and one most older write-ups get wrong: the relationship between this limit and the underlying C stack changed in CPython 3.12. Through 3.11, every Python-to-Python call also consumed a C-stack frame, so setting setrecursionlimit too high could segfault the interpreter (an unrecoverable crash) rather than raise RecursionError (a catchable exception); the limit’s whole purpose was to fire the Python guard before the C stack overflowed. In 3.12 (CPython issue GH-91079), Python-to-Python calls no longer push C-stack frames, and C-level recursion (into builtins, the regex engine, etc.) is policed by a separate, hardcoded limit independent of setrecursionlimit. The Python 3.12 release notes state it directly: “The recursion limit now applies only to Python code. Builtin functions do not use the recursion limit, but are protected by a different mechanism that prevents recursion from causing a virtual machine crash” (What’s New in Python 3.12). See Recursion Depth Limits §4 for the full mechanism and the still-incorrect sys docstring this changed out from under.

4.3 Why TCO Matters

In Scheme, you can write:

(define (loop n)
  (if (= n 0) 'done (loop (- n 1))))
(loop 1000000)   ; runs in O(1) stack space — TCO turns it into a loop

In Python, the same pattern crashes:

def loop(n):
    if n == 0: return 'done'
    return loop(n - 1)
loop(1_000_000)  # RecursionError: maximum recursion depth exceeded

This is why idiomatic Python uses iteration for what would be tail-recursive in Scheme. The language’s design forces it.

5. The “Every Recursive Algorithm Can Be Made Iterative” Theorem

Yes, you can always convert recursion to iteration. The general technique: simulate the call stack with an explicit stack data structure. Each recursive call becomes a “push a state onto the stack”; each return becomes a “pop the stack.” This is fundamental to the equivalence of recursive and iterative computation (any Turing machine can be simulated with a stack-based pushdown automaton, and vice versa for context-free language recognition).

The cost of this conversion: you trade implicit stack frames (managed by the runtime) for explicit stack data (managed by you). The total space usage is the same Θ(d) where d is the recursion depth, but it’s now in heap memory (the explicit stack) rather than the system stack — which is effectively unbounded (bounded by available RAM, not by an arbitrary ~1 MB / 1000-frame ceiling).

5.1 Pattern 1 — Tail Recursion → Loop

When a function tail-recurses, you replace the recursion with a loop and an accumulator:

# Recursive (tail form)
def sum_tail(n, acc=0):
    if n == 0: return acc
    return sum_tail(n - 1, acc + n)
 
# Iterative
def sum_iter(n):
    acc = 0
    while n > 0:
        acc += n
        n -= 1
    return acc

Mechanical translation: each “tail call argument” becomes “loop variable update.” This is what TCO would have done for you in Scheme.

5.2 Pattern 2 — Linear Recursion (Non-Tail) → Loop with Accumulator

If the recursion does post-processing (e.g., return x + f(rest)), you can usually rewrite by introducing an accumulator:

# Non-tail: result is multiplied by n after the recursive call returns
def fact_rec(n):
    if n <= 1: return 1
    return n * fact_rec(n - 1)
 
# Iterative with accumulator
def fact_iter(n):
    acc = 1
    for i in range(2, n + 1):
        acc *= i
    return acc
 
# Tail-recursive (would work with TCO; just illustration in Python)
def fact_tail(n, acc=1):
    if n <= 1: return acc
    return fact_tail(n - 1, acc * n)

The accumulator pattern is the general recipe for converting linear recursion to iteration: figure out what’s being accumulated as the recursion unwinds, and accumulate it forward instead.

5.3 Pattern 3 — Tree Recursion → Explicit Stack

This is the canonical case where the recursive version is dramatically clearer than the iterative one. Take depth-first search of a binary tree:

# Recursive DFS
def dfs_rec(node):
    if node is None: return
    process(node)
    dfs_rec(node.left)
    dfs_rec(node.right)

To iterate, simulate the call stack with a Python list:

# Iterative DFS using explicit stack
def dfs_iter(root):
    if root is None: return
    stack = [root]
    while stack:
        node = stack.pop()
        process(node)
        # Push right first, so left is processed first (LIFO order)
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)

The order-reversal (“push right first”) is critical: a stack is LIFO, so the most-recently-pushed item is popped first. To process left before right, push right first, then left is on top.

A common bug: pushing children in the wrong order, getting a right-then-left pre-order traversal where left-then-right was expected. Always re-check the LIFO direction.

5.4 Pattern 4 — Iterative In-Order and Post-Order

Pre-order DFS is easy iteratively (above). In-order and post-order require more bookkeeping — you have to return to a node after visiting its children, which the recursive call stack handled for free.

Iterative in-order traversal of a Binary Search Tree:

def inorder_iter(root):
    stack = []
    node = root
    while stack or node is not None:
        # Walk left as far as possible, pushing along the way
        while node is not None:
            stack.append(node)
            node = node.left
        # Process the leftmost unprocessed node
        node = stack.pop()
        process(node)
        # Then explore its right subtree
        node = node.right

This is the canonical “in-order with explicit stack” pattern. It runs in O(n) time and O(h) auxiliary space where h is tree height.

Iterative post-order is the trickiest — you need to know whether you’re descending or ascending. Two common techniques: a “visited” flag per stack entry, or two stacks. See Tree Traversals for full details.

The lesson: tree-recursive algorithms can be made iterative, but the conversion gets uglier as the recursion structure becomes more complex.

6. The Canonical “Recursive DFS to Iterative DFS” Walkthrough

This is the single most important conversion to know cold for interviews. Most candidates can recite what you do (use an explicit stack) but mess up the implementation. Here is the careful walkthrough.

6.1 Recursive Reference

def dfs(graph, start, visited):
    if start in visited: return
    visited.add(start)
    process(start)
    for neighbor in graph[start]:
        dfs(graph, neighbor, visited)

6.2 Iterative — First Attempt (Wrong)

A naive student converts directly:

def dfs_iter_WRONG(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        process(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

This works but the traversal order differs from the recursive version. Specifically: when iterating graph[node] in order n1, n2, n3 and pushing them, the last pushed is popped first, so the iterative DFS visits n3, n2, n1 (reversed). To match the recursive order exactly, push neighbors in reverse:

6.3 Iterative — Correct Order

def dfs_iter(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        process(node)
        # Push neighbors in REVERSE so the iteration order matches recursion
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)

For most graph problems the order doesn’t actually matter (DFS is DFS), but if you’re producing a sequence that must match a specific traversal order (e.g., expected output in a problem statement), the reversed() is critical.

6.4 The Subtle Trap — When You Mark Visited

Note we mark visited when popping, not when pushing. If you mark on push, you may push the same node twice (once via two different parents) before either pop happens, giving correct visited but wasted stack space. If you mark on pop, the stack can grow larger but the algorithm is simpler. CLRS (Ch. 22.3) presents the recursive version using a WHITE/GRAY/BLACK coloring scheme that marks on first visit; the iterative equivalent is tricky to get exactly right. For most interviews, the “mark on pop, skip if already visited” pattern is the safe choice.

6.5 Why Candidates Mess This Up

Three failure modes, in order of frequency:

  1. Wrong push/pop order. Pushing left before right in a tree DFS, when you wanted left-first traversal — but stack is LIFO so right comes first.
  2. Marking visited at the wrong time. Marking on push gives a different correctness contract than marking on pop; the recursive version is implicitly the latter.
  3. Forgetting to handle cycles in graphs. The recursive version’s if start in visited: return is essential. The iterative version often forgets the symmetric if node in visited: continue after popping, leading to revisits and incorrect output.

7. When Recursion Is Clearly Better

7.1 Tree and Graph Traversals

Recursive Depth-First Search, Tree Traversals (in-order, pre-order, post-order), and recursive descent parsing are all dramatically clearer recursively. The recursive structure mirrors the data structure’s recursive definition, and the call stack does the bookkeeping for you.

7.2 Divide-and-Conquer

Merge Sort, Quicksort, Master Theorem recurrences — recursion makes the divide-and-conquer structure explicit. Iterative merge sort exists (bottom-up merge sort) but is much less readable; iterative quicksort with explicit stack is uglier than the recursive version.

7.3 Backtracking

Permutations, combinations, N-Queens, Sudoku — see Backtracking Framework. Recursive backtracking is the canonical idiom; iterative versions exist but require explicit state stacks that add little but obscurity.

7.4 Recursive Data Definitions

When the data structure is defined recursively (a tree is a node with subtrees; a linked list is a node with a next-list), recursive code matches the definition. Linked List Reversal has elegant recursive forms even though iteration is also clean.

8. When Iteration Is Necessary

8.1 Deep Recursion Risks Stack Overflow

If your recursion depth could exceed the language’s stack limit, you must iterate.

  • Python: default 1000 Python-call recursion limit. A linked-list recursion on a 10,000-element list crashes with RecursionError. You can sys.setrecursionlimit(20_000); on CPython ≤3.11 the underlying C stack could segfault first if you raised it aggressively, while on 3.12+ pure Python-to-Python recursion no longer consumes C stack, so a high limit is safer (see Recursion Depth Limits).
  • JVM: with the default 1 MB (1024 KB) thread stack on 64-bit HotSpot, the achievable depth is on the order of 10⁴–10⁵ frames depending on frame size. Java tree algorithms on highly skewed trees can throw StackOverflowError.
  • Embedded systems: 1–10 KB stack typical. Recursion is essentially banned.

8.2 Tail Recursion in Non-TCO Languages

A tail-recursive function in Python that should be O(1) stack runs in O(n) because Python doesn’t optimize. If n is large, you must iterate manually. This is the most common reason to convert tail recursion to iteration in Python.

8.3 Real-Time Constraints

Recursion’s stack-frame allocation has a small overhead per call (a few hundred CPU cycles in Python; tens of cycles in C). For tight inner loops or hot real-time paths, the overhead matters. Iteration’s loop overhead is generally lower.

8.4 Memory-Bounded Environments

Where heap is more flexible than stack — most programs have ~8 MB of stack but gigabytes of heap available. Converting to iteration with an explicit heap-allocated stack lets you handle inputs that would blow the call stack.

9. Tail Recursion via the Accumulator Pattern

The general recipe for converting a non-tail recursive function to a tail-recursive one:

  1. Add an accumulator parameter that carries the “result so far.”
  2. Move the post-processing (x + f(rest)) into the accumulator update (acc + x, passed forward).
  3. Base case returns the accumulator instead of a constant.

Example — list length:

# Non-tail: 1 + length_rec(rest) requires post-addition
def length_rec(lst):
    if not lst: return 0
    return 1 + length_rec(lst[1:])
 
# Tail: accumulator carries length so far
def length_tail(lst, acc=0):
    if not lst: return acc
    return length_tail(lst[1:], acc + 1)

In a TCO language (Scheme), the tail version runs in O(1) stack. In Python, both run in O(n) stack — but the tail version is also trivially convertible to a loop:

def length_iter(lst):
    acc = 0
    while lst:
        acc += 1
        lst = lst[1:]   # NB: O(n) per slice, so this whole thing is O(n²) — actual O(n) loop would just iterate
    return acc

(Note lst[1:] is itself O(n) in Python — see Space Complexity. The right iterative version uses for x in lst: acc += 1 or len(lst). The point here is the control-flow pattern, not the actual best implementation of length.)

10. Pseudocode Recipe — Convert Recursion to Iteration

recursive_to_iterative(f):
    if f is tail-recursive:
        replace recursive call with loop variable update
        return as a while/for loop
    else:
        introduce explicit stack
        for each recursive call, push state onto stack
        for each return, pop stack and continue
        loop until stack is empty

The stack contents must capture everything the recursive call would have remembered: parameter values, local variables, and a “phase” indicator (am I before or after the recursive sub-call?) for non-tail recursions. This phase indicator is what makes iterative post-order traversal painful.

11. Pitfalls

11.1 Assuming Python Has TCO

It does not. A tail-recursive O(n) function still uses O(n) stack and crashes at depth ~1000. If you wrote a tail-recursive solution in an interview thinking it was efficient, you have a bug.

11.2 Off-By-One in the Recursion Limit

sys.setrecursionlimit(N) sets the limit, but Python’s frame inspection can use up frames itself. Don’t push to within 1 of the limit. See Off-By-One Errors — Survival Guide.

11.3 Wrong Push Order in Iterative DFS

Most-failed conversion bug. Stack is LIFO. To match recursive f(left); f(right), push right then left. Always trace through a 3-node example to verify.

11.4 Wrong Visited-Check Position

Mark visited on pop (after taking off the stack), not on push, in the iterative DFS pattern — unless you also check if not visited before pushing, in which case you can mark on push. Pick a consistent strategy and stick to it.

11.5 Forgetting Iterative Limits

Iteration uses heap memory but the heap is bounded too. An iterative DFS on a graph with 10^9 nodes still exhausts memory. The conversion fixes the stack overflow problem, not the memory budget problem.

11.6 Slow Slicing Confusion

lst[1:] in Python creates a copy in O(n). Recursive solutions that pass lst[1:] to themselves are O(n²) time, not O(n). Use indices instead: f(lst, i + 1) is O(1) per call.

11.7 Iterative Code Becomes Less Readable

There’s a real trade-off. An iterative DFS with explicit stack management is harder to read and debug than the 4-line recursive version. Use iteration only when you need to (depth, performance), not by default.

11.8 Tail Recursion in Wrong Position

return f(...) + 1 is not a tail call — the + 1 is post-processing. Compilers (in TCO languages) only optimize calls in exact tail position: return f(...) with nothing else. A common student mistake is to claim a function is tail-recursive when there’s still a final addition or wrapping.

12. Diagram — Recursive Tree-DFS vs Iterative-with-Stack

flowchart LR
    subgraph "Recursive DFS"
      direction TB
      R0["dfs(A)"]
      R1["dfs(B)"]
      R2["dfs(D)"]
      R3["dfs(E)"]
      R4["dfs(C)"]
      R0 -->|"call"| R1
      R1 -->|"call"| R2
      R1 -->|"call"| R3
      R0 -->|"call"| R4
      style R0 fill:#cfd
      style R1 fill:#cdf
      style R2 fill:#cdf
      style R3 fill:#cdf
      style R4 fill:#cdf
    end

    subgraph "Iterative DFS"
      direction TB
      S0["push A"]
      S1["pop A; process A; push C, B"]
      S2["pop B; process B; push E, D"]
      S3["pop D; process D"]
      S4["pop E; process E"]
      S5["pop C; process C"]
      S0 --> S1 --> S2 --> S3 --> S4 --> S5
    end

What this diagram shows. On the left is the recursive DFS where each call adds a new stack frame and returns when done — the call stack is the runtime’s responsibility. On the right is the iterative DFS using an explicit stack of nodes. The order of operations is the same in both — A, B, D, E, C are visited pre-order — but in the iterative version we must manually push and pop, and we must push children in reverse order (push C before B, push E before D) so that the LIFO stack pops them in the desired order. The same Θ(n) total space is used in both (recursion stack vs explicit stack), but the iterative version’s stack is on the heap and therefore not constrained by the language’s recursion limit.

13. Common Interview Problems

ProblemRecursiveIterativeWhich is better?
Tree pre/in/post-orderNatural, 3 linesExplicit stack, 10–15 linesRecursive unless tree is deep
Graph DFS / cycle detectionNaturalExplicit stackRecursive for sparse, shallow; iterative for very deep
Linked List ReversalElegant, but O(n) stackO(1) stack iterativeIterative usually
Binary SearchTail-recursive, cleanSame time, O(1) stackIterative (Python lacks TCO)
Merge SortNatural divide-and-conquerBottom-up iterative possibleRecursive (clearer)
QuicksortRecursive partitionIterative with explicit stackRecursive
Generate permutations / combinationsBacktracking is recursiveIterative is awkwardRecursive
Iterative deepening DFSRecursive inner DFS, iterative deepening loopBothHybrid

14. Open Questions

  • When does Python’s underlying C stack run out before the sys.setrecursionlimit() check fires? On CPython ≤3.11 this depended on the call graph and stack-allocated buffers and could occur well before setrecursionlimit’s value if the limit had been raised. On 3.12+ Python-to-Python recursion is decoupled from the C stack, so this concern now applies mainly to recursion that passes through C (builtins, the re engine), guarded by a separate hardcoded C-recursion limit. See Recursion Depth Limits §4.
  • Does Python 3.11+‘s lighter _PyInterpreterFrame change the per-frame size? Yes — frames are smaller and no longer per-call heap objects (see PEP 659 and the CPython interpreter internals doc) — but TCO is still not implemented and the default Python recursion limit remains 1000.
  • Is there a clean way to make Python tail-recursive code work without the recursion limit? Trampolining (returning a thunk and looping outside) is the standard hack but ugly. Continuation-passing style is theoretically equivalent. In practice, just write a loop.

15. See Also

Graph View

Backlinks