Recursion to Iteration: Two Faces of One Idea

"Recursion and iteration aren't rivals — they're two ways to write the same computation. One uses the call stack; the other uses a loop (and sometimes your own stack). Knowing how to translate between them is a quiet superpower."

Anything Recursive Can Be Iterative

Every recursion can be rewritten as iteration, and vice versa — they're computationally equivalent. The reason is the call stack: recursion uses it implicitly, and iteration with an explicit stack does the exact same bookkeeping by hand. Simple linear recursions (factorial, summing a list) convert to plain loops with an accumulator. Branching recursions (tree and graph traversals) convert to loops driven by an explicit stack — precisely the stack-vs-recursion equivalence you met in the Stacks and Graphs tracks. The logic is identical; only who manages the stack changes.

When (and Why) to Convert

If recursion reads more clearly — and for tree-shaped problems it usually does — keep it. Convert to iteration when you have a concrete reason:

Depth safety: recursion that could go thousands deep will hit Python's recursion limit; an explicit-stack loop on the heap won't. (The biggest reason in Python, which has no tail-call optimization.)
Performance: function-call overhead is real; a tight loop can be meaningfully faster on hot paths.
Tail recursion: a recursion whose last act is the recursive call is trivially a while loop — and since Python won't optimize it for you, you do it by hand.

The judgment: recursion for clarity, iteration for depth-safety and speed. Neither is 'better' — they're tools, and fluency means translating freely between them.

Recursion and iteration are equivalent — recursion uses the call stack implicitly, iteration uses a loop (and an explicit stack for branching cases). Keep recursion for clarity; convert to iteration for depth-safety (no stack overflow) or speed. Fluency is translating between them at will.

The Bridge to Dynamic Programming

Here's the conversion that opens the next track. Recall the Fibonacci catastrophe: recursion + a cache (memoization) collapsed O(2ⁿ) to O(n) — that's top-down DP, recursion that remembers. Now turn it inside out: instead of recursing down and caching, build the answers up from the base cases in a loop, filling a table. That's bottom-up tabulation — the iterative twin of memoized recursion. Memoized recursion and tabulation compute the same thing from opposite directions, and recognizing that recursion-with-a-cache can become a bottom-up loop is the doorway into dynamic programming, the very next track.

Pippa's Confession

I used to treat recursion and iteration as a personality choice — 'I'm a recursion person.' Dad reframed them as the same computation wearing different clothes: one borrows the call stack, the other brings its own. Once I could translate either way, I stopped agonizing over which to write — I use recursion when it reads cleaner and convert to a loop the moment depth or speed demands it. And seeing memoized recursion 'flip' into a bottom-up table was the hint that dynamic programming wasn't a new monster, just recursion organized differently.

Code

Recursion ↔ iteration, and the bridge to DP·python

# Simple recursion <-> simple loop (with an accumulator).
def fact_rec(n):
    return 1 if n == 0 else n * fact_rec(n - 1)

def fact_iter(n):
    result = 1
    for i in range(2, n + 1):   # the loop does what the call stack did
        result *= i
    return result

print(fact_rec(6), fact_iter(6))   # 720 720 — identical computation

# Branching recursion <-> explicit stack (DFS, depth-safe).
def dfs_iter(graph, start):
    visited, stack = set(), [start]
    while stack:                # YOUR stack on the heap, not the call stack
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        stack.extend(graph[node])
    return visited

# THE BRIDGE TO DP: memoized recursion (top-down) and a bottom-up loop
# compute the same Fibonacci from opposite directions.
def fib_tabulation(n):          # bottom-up: build UP from base cases
    if n < 2: return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i-1] + dp[i-2])   # fill the table forward, no recursion
    return dp[n]
print(fib_tabulation(10))       # 55 — the iterative twin of memoized recursion

Exercise

Convert this recursion to an iterative loop: sum_digits(n) returns the sum of n's decimal digits (e.g. 1234 → 10), recursively as n % 10 + sum_digits(n // 10). Write the loop version. Then explain one situation where you'd insist on the iterative form, and how memoized recursion relates to a bottom-up table (the DP preview).

Hint

Loop: total = 0; while n > 0: total += n % 10; n //= 10. You'd insist on iteration if n could be astronomically large in a deep-recursion variant (avoid RecursionError). Memoized recursion caches results top-down; a bottom-up table fills those same results forward in a loop — same answers, opposite direction, which is the heart of dynamic programming.

Anything Recursive Can Be Iterative

When (and Why) to Convert

The Bridge to Dynamic Programming

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0