From recursion to iteration

Recursion uses the language's call stack to remember unfinished work. You can do the same job with a loop and an explicit stack: push what you would have called, pop to process it, and store whatever a frame would have remembered (such as which child to visit next) in the stack entries.

Some recursions need no stack at all. A tail-recursive function, where the recursive call is the very last thing it does, can become a simple loop that updates its variables. Memoized recursion over states can become bottom-up tabulation that fills a table in order. Python does not optimise tail calls, so in Python these rewrites are how you handle large inputs.

1. 1Identify what each recursive frame remembers: its arguments, local variables and where to continue after each call returns.
2. 2Create a stack and push the initial call's state.
3. 3Loop while the stack is not empty: pop a state, do the work that comes before the recursive calls, and push the states for the calls. Push children in reverse order if the visiting order matters.
4. 4If work must happen after a child returns (in-order or post-order), either push a marker such as (node, visited=True) or use a pattern like 'go left until null, then pop'.
5. 5For tail recursion, replace the call with reassigning the parameters and looping. For memoized recursion, fill a table from the base cases upward instead.

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

def inorder_recursive(node, out):
    if node:
        inorder_recursive(node.left, out)
        out.append(node.val)
        inorder_recursive(node.right, out)
    return out

def inorder_iterative(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                 # go left, remembering the path
            stack.append(node)
            node = node.left
        node = stack.pop()          # the "return" from the left call
        out.append(node.val)
        node = node.right           # then handle the right subtree
    return out

root = Node(4, Node(2, Node(1), Node(3)), Node(5))
print(inorder_recursive(root, []))  # [1, 2, 3, 4, 5]
print(inorder_iterative(root))      # [1, 2, 3, 4, 5]

Both functions visit the same nodes in the same order. In the iterative version the stack holds exactly the nodes whose left subtree is in progress, which is what the recursive call stack would hold, but it lives in a Python list that is limited only by memory.

Cost: Converting does not change the time complexity. Extra space stays O(depth) for the stack, but on the heap instead of the call stack; tail-recursion loops and rolling-array tabulation can reduce it to O(1).