Any Recursion Can Be Converted to Iteration (With Explicit Stack) - Recursion vs Iteration | OneNoughtOne

0/361

Data Structures & AlgorithmsRecursion

Recursion vs Iteration

LevelIntermediate

Duration60 mins

TopicRecursion

1 / 4

Any Recursion Can Be Converted to Iteration (With Explicit Stack)

The Fundamental Equivalence

One of the most profound insights in computer science is this: every recursive algorithm has an equivalent iterative counterpart. This isn't merely a convenience—it's a mathematical certainty that reveals something deep about the nature of computation itself.

When you write a recursive function, the programming language runtime silently manages a call stack for you. Each recursive call pushes a new frame onto this stack, storing local variables, parameters, and return addresses. When you convert recursion to iteration, you're simply making this implicit stack explicit—taking manual control of what the runtime previously handled automatically.

This equivalence has profound practical implications. It means you're never forced to use recursion; any problem solvable recursively can be solved iteratively. Conversely, it means recursion isn't "magic"—it's a convenient notation for a particular pattern of stack-based computation.

What You Will Learn

By the end of this page, you will understand why recursion and iteration are fundamentally equivalent, how the call stack enables recursion, and how to manually simulate this mechanism using an explicit stack. You'll gain the foundational knowledge to convert any recursive algorithm to an iterative one.

The Call Stack Revelation

To understand why recursion can always be converted to iteration, we must first understand what recursion actually is at the machine level. When you call a recursive function, you're not invoking some mystical self-referential magic—you're simply making function calls, each of which gets added to a data structure called the call stack.

Consider what happens when you execute factorial(5):

factorial_recursive.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
 
# When we call factorial(5), the call stack evolves as follows:
# 
# Call factorial(5) → Push frame {n=5}
#   Call factorial(4) → Push frame {n=4}
#     Call factorial(3) → Push frame {n=3}
#       Call factorial(2) → Push frame {n=2}
#         Call factorial(1) → Push frame {n=1}
#           Base case reached → Return 1
#         Pop frame {n=1} → Return 1
#       Pop frame {n=2} → Return 2 * 1 = 2
#     Pop frame {n=3} → Return 3 * 2 = 6
#   Pop frame {n=4} → Return 4 * 6 = 24
# Pop frame {n=5} → Return 5 * 24 = 120

Key observation: The call stack is just a stack data structure—the same stack we studied in the Stacks chapter. Each "frame" pushed onto the stack contains:

Parameters — The values passed to this particular function call (e.g., n=5)
Local variables — Any variables declared within the function
Return address — Where to resume execution after the function returns
Saved computation state — Any intermediate results waiting for the recursive call to complete

This is the crucial insight: the runtime is using a stack to manage your recursive calls. If the runtime can do it, so can you—explicitly.

The Stack Is Not Magic

Every programming language implements function calls using a call stack. When you write recursive code, you're not accessing some special recursive facility—you're just making function calls that happen to call the same function. The 'recursion' is an emergent property of the call stack's LIFO behavior.

The Conversion Theorem

The theoretical foundation for recursion-to-iteration conversion rests on a fundamental result in computability theory: any computation expressible with recursion can be expressed with iteration and explicit state management.

This isn't just an empirical observation—it's provable. Both recursive and iterative programs are equivalent in computational power to Turing machines. Since they compute the same class of functions, anything one can do, the other can do.

But the proof doesn't just tell us conversion is possible—it tells us how to do it. The systematic approach is:

Systematic Conversion Steps

•Identify the state being tracked by the call stack — What parameters, local variables, and intermediate results does each recursive call need to preserve?
•Create an explicit stack data structure — This stack will hold objects/tuples representing the state that would be in each call frame.
•Replace recursive calls with push operations — Instead of calling the function recursively, push the new state onto your stack.
•Use a loop that processes until the stack is empty — The loop body simulates what the function body does, popping states and potentially pushing new ones.
•Handle return values explicitly — Store intermediate results where subsequent loop iterations can access them.

The general pattern:

Every recursive function can be decomposed into:

State — The information passed between recursive calls (parameters + local variables)
Transitions — The logic that determines what recursive calls to make (push operations)
Base case handling — The termination condition and what to return
Aggregation — How results from recursive calls are combined

When we convert to iteration, we make all of these explicit:

conversion_template.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# RECURSIVE PATTERN:
def recursive_function(input):
    if base_case(input):
        return base_result
    
    smaller_input = reduce(input)
    sub_result = recursive_function(smaller_input)  # Recursive call
    return combine(input, sub_result)
 
# ITERATIVE EQUIVALENT:
def iterative_function(input):
    # Stack holds tuples of (state, phase)
    # phase indicates whether we're "descending" or "returning"
    stack = [(input, "descend")]
    results = {}  # Store intermediate results
    
    while stack:
        current, phase = stack.pop()
        
        if phase == "descend":
            if base_case(current):
                results[current] = base_result
            else:
                smaller = reduce(current)
                # Push current to handle after sub-result is ready
                stack.append((current, "combine"))
                # Push the subproblem to solve first
                stack.append((smaller, "descend"))
        
        elif phase == "combine":
            smaller = reduce(current)
            sub_result = results[smaller]
            results[current] = combine(current, sub_result)
    
    return results[input]

Phase Tracking

The 'phase' concept is crucial for non-tail recursion. Before a recursive call, we're 'descending' into subproblems. After the recursive call returns, we're in the 'combine' phase. Our explicit stack must track which phase we're in for each piece of state.

Converting Factorial — Step by Step

Let's apply the conversion process to the factorial function. This is a simple case, but we'll be thorough to establish the method clearly.

Step 1: Analyze the recursive structure

factorial(n) = n × factorial(n-1)  [when n > 1]
factorial(1) = 1                    [base case]

Step 2: Identify the state

Parameter: n
Intermediate computation: We need n available to multiply after the recursive call returns
Return value: The factorial result

Step 3: Determine the conversion approach

For factorial, we have a key insight: this is tail-recursive optimizable. We can actually convert it to a simple loop without a full explicit stack. But let's first show the general stack-based approach, then simplify.

factorial_iterative_full.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# APPROACH 1: Full explicit stack simulation
# This demonstrates the general technique
 
def factorial_stack_based(n):
    """
    Converts factorial recursion to iteration using explicit stack.
    Each stack entry is (value, phase) where phase is 'compute' or 'multiply'.
    """
    if n <= 1:
        return 1
    
    stack = []
    result = 1
    
    # Phase 1: Push all values onto the stack (simulating the descent)
    current = n
    while current > 1:
        stack.append(current)
        current -= 1
    
    # Phase 2: Pop and multiply (simulating the return/combine phase)
    while stack:
        value = stack.pop()
        result *= value
    
    return result
 
 
# APPROACH 2: Recognizing this is tail-recursive optimizable
# The multiplication can be done on the way down, not just up
 
def factorial_accumulator(n):
    """
    Tail-recursive style converted to simple iteration.
    Uses an accumulator to avoid needing a stack entirely.
    """
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result
 
 
# Verification
print(f"Stack-based: factorial(5) = {factorial_stack_based(5)}")  # 120
print(f"Accumulator: factorial(5) = {factorial_accumulator(5)}")  # 120

Why does the simple loop work for factorial?

Factorial has a special property: the order of multiplication doesn't matter (multiplication is associative and commutative). This means we can compute:

1 × 2 × 3 × 4 × 5 (bottom-up)

instead of:

5 × (4 × (3 × (2 × 1))) (top-down, how recursion naturally computes it)

But not all recursive functions have this property. For functions where the order matters or where we truly need to "wait" for subproblem results, the explicit stack is necessary.

Simple Cases Often Simplify

For many recursive functions with single recursive calls and associative operations, the explicit stack can be simplified to a single loop with an accumulator. But the general stack-based technique always works, even when such simplifications aren't possible.

Converting Tree Traversal — The Real Test

Factorial is too simple to demonstrate the full power of stack-based conversion. Let's tackle something more challenging: binary tree traversal.

With tree traversal, we have:

Branching (the function calls itself twice—once for left, once for right)
Order sensitivity (inorder, preorder, and postorder give different results)
Real need to "remember" where we were

This is where explicit stacks truly shine.

tree_traversal_conversion.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
# ============================================
# RECURSIVE VERSION: Inorder Traversal
# ============================================
def inorder_recursive(root):
    """Left → Root → Right"""
    result = []
    
    def traverse(node):
        if node is None:
            return
        traverse(node.left)      # First, go left
        result.append(node.val)  # Then, visit root
        traverse(node.right)     # Finally, go right
    
    traverse(root)
    return result
 
 
# ============================================
# ITERATIVE VERSION: Inorder Traversal
# ============================================
def inorder_iterative(root):
    """
    Explicit stack simulates the call stack.
    Key insight: We go left as far as possible first,
    then visit, then go right.
    """
    result = []
    stack = []
    current = root
    
    while current is not None or stack:
        # Go left as far as possible, pushing nodes onto stack
        while current is not None:
            stack.append(current)
            current = current.left
        
        # Pop the next node to visit
        current = stack.pop()
        result.append(current.val)  # Visit
        
        # Move to right subtree
        current = current.right
    
    return result
 
 
# ============================================
# RECURSIVE VERSION: Preorder Traversal
# ============================================
def preorder_recursive(root):
    """Root → Left → Right"""
    result = []
    
    def traverse(node):
        if node is None:
            return
        result.append(node.val)  # First, visit root
        traverse(node.left)      # Then, go left
        traverse(node.right)     # Finally, go right
    
    traverse(root)
    return result
 
 
# ============================================
# ITERATIVE VERSION: Preorder Traversal
# ============================================
def preorder_iterative(root):
    """
    Preorder is simpler: visit immediately, then push right before left
    (so left gets processed first, due to LIFO).
    """
    if root is None:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)  # Visit immediately
        
        # Push right first, so left gets processed first (LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result
 
 
# ============================================
# RECURSIVE VERSION: Postorder Traversal
# ============================================
def postorder_recursive(root):
    """Left → Right → Root"""
    result = []
    
    def traverse(node):
        if node is None:
            return
        traverse(node.left)      # First, go left
        traverse(node.right)     # Then, go right
        result.append(node.val)  # Finally, visit root
    
    traverse(root)
    return result
 
 
# ============================================
# ITERATIVE VERSION: Postorder Traversal (with tracking)
# ============================================
def postorder_iterative(root):
    """
    Postorder is trickiest iteratively because we must visit
    children BEFORE the parent. We track whether we've already
    processed a node's children.
    """
    if root is None:
        return []
    
    result = []
    stack = [(root, False)]  # (node, children_processed)
    
    while stack:
        node, processed = stack.pop()
        
        if processed:
            # We've already done children, now visit this node
            result.append(node.val)
        else:
            # Re-push with processed=True (to visit after children)
            stack.append((node, True))
            
            # Push right, then left (so left is processed first)
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    
    return result
 
 
# ============================================
# Test with a sample tree
# ============================================
#        1
#       / \
#      2   3
#     / \
#    4   5
 
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
 
print(f"Inorder Recursive:  {inorder_recursive(root)}")   # [4, 2, 5, 1, 3]
print(f"Inorder Iterative:  {inorder_iterative(root)}")   # [4, 2, 5, 1, 3]
print(f"Preorder Recursive: {preorder_recursive(root)}")  # [1, 2, 4, 5, 3]
print(f"Preorder Iterative: {preorder_iterative(root)}")  # [1, 2, 4, 5, 3]
print(f"Postorder Recursive: {postorder_recursive(root)}")# [4, 5, 2, 3, 1]
print(f"Postorder Iterative: {postorder_iterative(root)}")# [4, 5, 2, 3, 1]

Key insights from tree traversal conversion:

The stack remembers "where we were" — Just as the call stack tracks pending return addresses, our explicit stack tracks which nodes we still need to process.
Different traversal orders require different stack strategies — Preorder is easy (visit immediately, push children). Inorder requires going left first inside the loop. Postorder needs phase tracking.
Push order matters — Due to LIFO, if you want to process left before right, push right first.
Postorder is hardest — It requires visiting children before the parent. We solve this by tracking a "processed" flag for each node. This directly mimics what the call stack does: remembering that we're waiting for child calls to return before we can finish the parent call.

The General Transformation Algorithm

While specific recursive functions can be converted using tailored insights, there's a general algorithm that works for any recursive function. This is particularly valuable for complex recursions with multiple recursive calls, complex base cases, or intricate state passing.

The CPS-style transformation:

The most general technique is inspired by Continuation-Passing Style (CPS), a program transformation technique from functional programming. The idea: instead of relying on the call stack to remember "what to do next," we explicitly encode "what to do next" as data.

general_transformation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
# ============================================
# GENERAL PATTERN: Any Recursive Function
# ============================================
 
# Original recursive function:
# def recursive_func(params):
#     if base_case(params):
#         return base_value
#     
#     # Pre-recursive work
#     pre_result = do_pre_work(params)
#     
#     # Recursive call(s)
#     rec_result1 = recursive_func(modified_params1)
#     rec_result2 = recursive_func(modified_params2)  # if multiple calls
#     
#     # Post-recursive work (uses recursive results)
#     final_result = combine(pre_result, rec_result1, rec_result2)
#     return final_result
 
 
# ============================================
# STEP 1: Define stack frame structure
# ============================================
# A stack frame must capture:
# - The phase (which stage of computation)
# - The parameters for this call
# - Any intermediate results from previous phases
# - Any saved state needed for later phases
 
from dataclasses import dataclass
from typing import Any, List
 
@dataclass
class StackFrame:
    phase: str           # 'init', 'after_call1', 'after_call2', etc.
    params: Any          # The original parameters
    saved_state: Any     # Pre-recursive work results, intermediate values
    results: List[Any]   # Results from completed recursive calls
 
 
# ============================================
# STEP 2: Implement the iterative version
# ============================================
 
def iterative_general(initial_params):
    """
    General iterative simulation of recursion.
    Uses explicit stack with phase tracking.
    """
    # Stack of frames; each frame represents a call
    stack = [StackFrame(phase='init', params=initial_params, saved_state=None, results=[])]
    
    # The value being "returned" by the most recently completed call
    return_value = None
    
    while stack:
        frame = stack[-1]  # Peek at top (don't pop yet)
        
        if frame.phase == 'init':
            # ── Phase 1: Initial entry ──
            if base_case(frame.params):
                # Base case: compute result and "return"
                return_value = base_value(frame.params)
                stack.pop()  # This call is done
            else:
                # Pre-recursive work
                frame.saved_state = do_pre_work(frame.params)
                frame.phase = 'make_call1'
        
        elif frame.phase == 'make_call1':
            # ── Phase 2: Make first recursive call ──
            new_params = modify_params1(frame.params)
            frame.phase = 'after_call1'
            # Push the new recursive call
            stack.append(StackFrame(phase='init', params=new_params, saved_state=None, results=[]))
        
        elif frame.phase == 'after_call1':
            # ── Phase 3: First recursive call returned ──
            frame.results.append(return_value)  # Capture the return value
            
            if has_second_recursive_call:
                frame.phase = 'make_call2'
            else:
                frame.phase = 'combine'
        
        elif frame.phase == 'make_call2':
            # ── Phase 4: Make second recursive call ──
            new_params = modify_params2(frame.params)
            frame.phase = 'after_call2'
            stack.append(StackFrame(phase='init', params=new_params, saved_state=None, results=[]))
        
        elif frame.phase == 'after_call2':
            # ── Phase 5: Second recursive call returned ──
            frame.results.append(return_value)
            frame.phase = 'combine'
        
        elif frame.phase == 'combine':
            # ── Phase 6: All recursive calls done, combine results ──
            return_value = combine(frame.saved_state, frame.results)
            stack.pop()  # This call is done
    
    return return_value
 
 
# ============================================
# CONCRETE EXAMPLE: Fibonacci with general pattern
# ============================================
 
def fib_recursive(n):
    """Standard recursive Fibonacci"""
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)
 
 
def fib_iterative_general(n):
    """Fibonacci using the general transformation pattern"""
    
    @dataclass
    class FibFrame:
        phase: str
        n: int
        first_result: int = 0
    
    stack = [FibFrame(phase='init', n=n)]
    return_value = 0
    
    while stack:
        frame = stack[-1]
        
        if frame.phase == 'init':
            if frame.n <= 1:
                return_value = frame.n
                stack.pop()
            else:
                frame.phase = 'after_first'
                stack.append(FibFrame(phase='init', n=frame.n - 1))
        
        elif frame.phase == 'after_first':
            frame.first_result = return_value
            frame.phase = 'after_second'
            stack.append(FibFrame(phase='init', n=frame.n - 2))
        
        elif frame.phase == 'after_second':
            return_value = frame.first_result + return_value
            stack.pop()
    
    return return_value
 
 
# Test
for i in range(10):
    assert fib_recursive(i) == fib_iterative_general(i)
print("Fibonacci: All tests passed!")

General Pattern Trade-offs

The general transformation always works, but it produces more complex code than tailored conversions. For simple cases (single recursive call, tail recursion), use simpler patterns. Reserve the general pattern for complex multi-branching recursions where simpler techniques fail.

Why Does This Work?

The conversion from recursion to iteration with an explicit stack works because of a fundamental property: the call stack is just a stack. There's nothing magical about recursion—it's syntactic sugar for a pattern of pushing and popping stack frames.

Let's be precise about what the call stack does:

Call Stack vs Explicit Stack Correspondence
Recursive Mechanism	Iterative Equivalent	Purpose
Function call	Push frame to stack	Start processing a subproblem
Local variables	Fields in stack frame object	Store state specific to this subproblem
Parameters	Fields in stack frame object	Input to the subproblem
Return address	Phase field in stack frame	Remember what to do when subproblem completes
Return value	Explicit variable (return_value)	Pass result back to caller
Returning from function	Pop frame from stack	Signal completion of subproblem
Function body execution	Switch/if on phase field	Execute the appropriate computation stage

The Turing equivalence:

Both recursive and iterative programs (with support for dynamic memory allocation, like stacks) are Turing-complete. This means they can compute exactly the same class of functions. The conversion isn't just a clever trick—it's a consequence of this theoretical equivalence.

Stack is the key:

Without a stack (or equivalent dynamic memory), iteration is strictly weaker than recursion. A simple loop with finite variables cannot compute everything a recursive function can. But once we add a stack, the power becomes equivalent.

This is why the explicit stack is essential for the conversion. The stack provides the unbounded memory needed to track arbitrarily deep nested computations.

Theoretical Foundation

This equivalence is formalized in the λ-calculus (basis of functional programming) and Turing machines (basis of imperative programming). Church and Turing independently proved these systems compute the same functions—the Church-Turing thesis. Every recursive program has an equivalent iterative program, and vice versa.

Practical Implications

Understanding that recursion and iteration are equivalent has important practical consequences for software engineering:

Key Practical Takeaways

•You're never forced into recursion — If stack overflow is a concern, you can always convert to iteration. No algorithm "requires" recursion; it's always a choice.
•You're never forced into iteration — If the recursive version is clearer and stack depth isn't a concern, use it. Readability has value.
•Stack space can be controlled — With an explicit stack, you can use heap memory instead of call stack memory. Heap is typically larger and doesn't cause stack overflow.
•Debugging becomes different — With explicit stacks, you can inspect the stack contents, serialize them, log them. The call stack is harder to examine.
•Performance characteristics may differ — Explicit stack operations may have different overhead than function calls, depending on the language runtime.
•Some languages optimize recursion — Languages with tail call optimization (Scheme, some functional languages) remove the stack overhead for tail-recursive functions, making them as efficient as loops.

When to use which:

The equivalence means the choice between recursion and iteration is not about capability—they can do the same things. The choice is about:

Clarity — Which version is easier to understand and maintain?
Performance — Which has less overhead in your specific context?
Constraints — Are there stack depth limitations? Memory constraints?
Tooling — Which is easier to debug, profile, or test?

We'll explore these tradeoffs in detail in the following pages of this module.

Page Complete

You now understand the fundamental equivalence between recursion and iteration. Every recursive algorithm can be converted to an iterative one using an explicit stack. This isn't a limitation—it's a capability. You have complete freedom to choose the approach that best fits each situation. In the next page, we'll explore when recursion provides greater clarity and expressiveness.