Recursion to Iteration: Converting Recursive Code

Recursion is elegant and intuitive for many problems, but it has practical limitations: stack overflow for deep recursion, function call overhead, and difficulty with certain optimizations. Knowing how to convert recursive code to iterative code is a fundamental skill that unlocks better performance and handles edge cases that recursion cannot.

Why convert recursion to iteration?

Stack overflow risk

Python has a default recursion limit of 1000. Processing a linked list of 10,000 nodes recursively will crash:

import sys
print(sys.getrecursionlimit())  # 1000

# This WILL crash for large inputs:
def sum_list_recursive(node):
    if node is None:
        return 0
    return node.val + sum_list_recursive(node.next)

# This NEVER crashes:
def sum_list_iterative(node):
    total = 0
    while node:
        total += node.val
        node = node.next
    return total

Performance overhead

Each function call creates a stack frame with local variables, return address, and parameters. Iterative solutions avoid this overhead:

import time

def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

def fib_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# fib_recursive(35) takes seconds
# fib_iterative(35) takes microseconds

Memory efficiency

Recursive DFS on a graph with 1 million nodes uses 1 million stack frames. Iterative DFS with an explicit stack uses the same memory but does not risk hitting the system stack limit.

Strategy 1: tail recursion to simple loop

Tail recursion is when the recursive call is the very last operation in the function. There is nothing to do after the recursive call returns.

# TAIL RECURSIVE
def factorial_tail(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)  # Last operation

# NOT tail recursive
def factorial_normal(n):
    if n <= 1:
        return 1
    return n * factorial_normal(n - 1)  # Must multiply AFTER return

Tail recursive functions convert directly to loops because there is no work left after the recursive call:

# Tail recursive -> Loop
def factorial_iterative(n):
    accumulator = 1
    while n > 1:
        accumulator *= n
        n -= 1
    return accumulator

print(factorial_iterative(10))  # 3628800

More tail recursion conversions

GCD (Euclidean algorithm):

# Recursive (already tail recursive)
def gcd_recursive(a, b):
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

# Iterative
def gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd_iterative(48, 18))  # 6

Binary search:

# Recursive
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# Iterative
def binary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

arr = [1, 3, 5, 7, 9, 11]
print(binary_search_iterative(arr, 7))  # 3

Power function:

# Recursive (tail with accumulator)
def power_recursive(base, exp, acc=1):
    if exp == 0:
        return acc
    if exp % 2 == 0:
        return power_recursive(base * base, exp // 2, acc)
    return power_recursive(base, exp - 1, acc * base)

# Iterative
def power_iterative(base, exp):
    result = 1
    while exp > 0:
        if exp % 2 == 1:
            result *= base
        base *= base
        exp //= 2
    return result

print(power_iterative(2, 10))  # 1024

Strategy 2: explicit stack

When recursion is not tail recursive, you need an explicit stack to simulate the call stack. The key insight: the system call stack stores the same information you can store in your own stack.

General conversion pattern

# Recursive version
def process_recursive(data):
    if base_case(data):
        return base_result

    # pre-processing
    result = process_recursive(smaller_data)
    # post-processing using result

    return final_result

# Iterative version with explicit stack
def process_iterative(data):
    stack = [initial_state]
    result = None

    while stack:
        state = stack.pop()

        if base_case(state):
            # Handle base case
            continue

        # Push states that need processing
        # Push in REVERSE order (stack is LIFO)
        stack.append(next_state)

Example: reverse a linked list

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# Recursive
def reverse_recursive(head):
    if head is None or head.next is None:
        return head

    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head


# Iterative
def reverse_iterative(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev

Example: flatten nested list

# Recursive
def flatten_recursive(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten_recursive(item))
        else:
            result.append(item)
    return result


# Iterative with explicit stack
def flatten_iterative(nested):
    stack = [nested]
    result = []

    while stack:
        current = stack.pop()

        if isinstance(current, list):
            # Push elements in reverse so first element is processed first
            for item in reversed(current):
                stack.append(item)
        else:
            result.append(current)

    return result


nested = [1, [2, [3, 4], 5], [6, 7]]
print(flatten_recursive(nested))   # [1, 2, 3, 4, 5, 6, 7]
print(flatten_iterative(nested))   # [1, 2, 3, 4, 5, 6, 7]

Strategy 3: iterative tree traversals

Tree traversals are the most common recursion-to-iteration conversion asked in interviews.

Preorder traversal (root, left, right)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# Recursive
def preorder_recursive(root):
    if not root:
        return []
    return ([root.val] +
            preorder_recursive(root.left) +
            preorder_recursive(root.right))


# Iterative
def preorder_iterative(root):
    """
    Iterative preorder using explicit stack.
    Push right first, then left (stack is LIFO).
    """
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

Inorder traversal (left, root, right)

This is trickier because we must process the left subtree before the current node.

# Iterative inorder
def inorder_iterative(root):
    """
    Go left as far as possible, process node, then go right.
    Time: O(n), Space: O(h) where h = height
    """
    result = []
    stack = []
    current = root

    while current or stack:
        # Go to the leftmost node
        while current:
            stack.append(current)
            current = current.left

        # Process the node
        current = stack.pop()
        result.append(current.val)

        # Move to right subtree
        current = current.right

    return result

Postorder traversal (left, right, root)

The trickiest of the three. Two approaches:

# Method 1: Modified preorder + reverse
def postorder_two_stacks(root):
    """
    Do a modified preorder (root, right, left) and reverse.
    """
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        # Push left first, then right (opposite of preorder)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return result[::-1]


# Method 2: Single stack with visited tracking
def postorder_single_stack(root):
    """
    Track the previously processed node to determine
    if we should process current or go deeper.
    """
    if not root:
        return []

    result = []
    stack = [root]
    prev = None

    while stack:
        current = stack[-1]

        # Going down: push children
        if prev is None or prev.left == current or prev.right == current:
            if current.left:
                stack.append(current.left)
            elif current.right:
                stack.append(current.right)
            else:
                result.append(stack.pop().val)
        # Coming up from left: go right or process
        elif current.left == prev:
            if current.right:
                stack.append(current.right)
            else:
                result.append(stack.pop().val)
        # Coming up from right: process
        else:
            result.append(stack.pop().val)

        prev = current

    return result

Morris traversal (O(1) space inorder)

Morris traversal achieves O(1) space by temporarily modifying tree pointers. No stack or recursion needed.

def morris_inorder(root):
    """
    Inorder traversal with O(1) extra space.
    Temporarily creates threads (links) back to the inorder successor.
    Time: O(n), Space: O(1)
    """
    result = []
    current = root

    while current:
        if current.left is None:
            # No left subtree: process and go right
            result.append(current.val)
            current = current.right
        else:
            # Find the inorder predecessor (rightmost in left subtree)
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if predecessor.right is None:
                # Create thread: link predecessor back to current
                predecessor.right = current
                current = current.left
            else:
                # Thread exists: we've returned via the thread
                # Remove thread and process current
                predecessor.right = None
                result.append(current.val)
                current = current.right

    return result

Strategy 4: DFS iterative

Graph DFS converts naturally to an iterative approach with an explicit stack.

# Recursive DFS
def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    result = [start]

    for neighbor in graph[start]:
        if neighbor not in visited:
            result.extend(dfs_recursive(graph, neighbor, visited))

    return result


# Iterative DFS
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []

    while stack:
        node = stack.pop()
        if node in visited:
            continue

        visited.add(node)
        result.append(node)

        # Push neighbors (reverse for consistent order with recursive)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)

    return result


graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [], 'E': [], 'F': []
}
print(dfs_recursive(graph, 'A'))  # ['A', 'B', 'D', 'E', 'C', 'F']
print(dfs_iterative(graph, 'A'))  # ['A', 'B', 'D', 'E', 'C', 'F']

Strategy 5: memoization as a bridge to DP

Memoized recursion (top-down DP) can be converted to iterative bottom-up DP. This eliminates recursion entirely and often improves cache performance.

Fibonacci: recursion to memoization to tabulation

# Step 1: Naive recursion - O(2^n) time
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


# Step 2: Memoized recursion (top-down DP) - O(n) time, O(n) space
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


# Step 3: Iterative tabulation (bottom-up DP) - O(n) time, O(n) space
def fib_table(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


# Step 4: Space-optimized iteration - O(n) time, O(1) space
def fib_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b


print(fib_optimized(50))  # 12586269025

Climbing stairs

# Recursive (with memoization)
def climb_stairs_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return n
    memo[n] = climb_stairs_memo(n - 1, memo) + climb_stairs_memo(n - 2, memo)
    return memo[n]


# Iterative
def climb_stairs_iterative(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b


print(climb_stairs_iterative(10))  # 89

Coin change

# Recursive with memoization
def coin_change_memo(coins, amount):
    memo = {}

    def dp(remaining):
        if remaining in memo:
            return memo[remaining]
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')

        result = float('inf')
        for coin in coins:
            result = min(result, 1 + dp(remaining - coin))

        memo[remaining] = result
        return result

    ans = dp(amount)
    return ans if ans != float('inf') else -1


# Iterative bottom-up
def coin_change_iterative(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1


print(coin_change_iterative([1, 5, 10, 25], 36))  # 3 (25 + 10 + 1)

Conversion decision guide

Recursion Type	Conversion Strategy	Difficulty
Tail recursion	Replace with while loop	Easy
Linear recursion (one call)	Explicit stack or loop	Easy
Binary recursion (two calls)	Explicit stack	Medium
Tree/graph DFS	Stack-based iteration	Medium
Backtracking	Stack with state objects	Hard
Mutual recursion	State machine	Hard
Memoized recursion	Bottom-up DP table	Medium

Common pitfalls

Pitfall 1: Forgetting to reverse push order for stacks.

# Stack is LIFO. To process children left-to-right:
# Push RIGHT first, then LEFT
stack.append(node.right)  # Pushed first, popped last
stack.append(node.left)   # Pushed last, popped first

Pitfall 2: Not handling the “work after recursive call” case.

# When there's work to do AFTER the recursive call,
# you need to push a "continuation" onto the stack
# or use the two-stack approach for postorder.

Pitfall 3: Infinite loops from not marking visited nodes.

# Always check visited BEFORE pushing to stack (graph DFS)
if neighbor not in visited:
    stack.append(neighbor)

Practice problems

Problem	Conversion Type	Difficulty
Factorial	Tail recursion -> loop	Easy
Fibonacci	Memo -> DP table	Easy
Binary Search	Tail recursion -> loop	Easy
Reverse Linked List (LC 206)	Linear -> iterative	Easy
Inorder Traversal (LC 94)	Binary -> stack	Medium
Flatten Nested List (LC 341)	Stack-based	Medium
DFS on graph	Stack-based	Medium
Postorder Traversal (LC 145)	Two stacks	Medium
Coin Change (LC 322)	Memo -> tabulation	Medium
Morris Inorder Traversal	Threading (no stack)	Hard

Key takeaways

1. Tail recursion converts directly to a while loop. Look for recursive calls that are the last operation.
2. Non-tail recursion needs an explicit stack. Push states in reverse order (LIFO).
3. Tree traversals have standard iterative patterns. Inorder uses the “go left, process, go right” pattern. Morris traversal achieves O(1) space.
4. Memoized recursion naturally converts to bottom-up DP by filling a table in dependency order.
5. Always prefer iterative for production code that might handle large inputs. Python’s 1000-call recursion limit is a real constraint.