Recursion to an Explicit Stack

The idea: do the call stack's job yourself

When a function calls itself, the language pushes a stack frame and pops it on return. Nothing about that is magic. You can keep the frames yourself: put them in a list, push one where the code would call, pop one where it would return, and loop until the list is empty. The result is the same, but the frames now live in a list on the heap instead of on the small, fixed-size call stack.

What a frame holds

The page sums a binary tree:

def total(node):
    l = total(node.left) if node.left else 0
    r = total(node.right) if node.right else 0
    return node.val + l + r

While total(3) runs, total(5) is paused in the middle of line 2. To finish later it needs three things: its arguments (node = 5), its locals (l and r) and its return address, the place in the code to resume, here "store the value in l and go on at line 3". That is a frame. Real frames also hold saved registers, but these three are what the algorithm needs (Demo: recursion, balanced tree).

The loop: peek, step, pop

Write the frame as an object and the return address as a field at, the next line to run. The loop looks at the top frame and runs one piece of it:

def total(root):
    stack = [Frame(root)]          # node, at=2, l=0, r=0
    while stack:                   # loop until empty
        f = stack[-1]
        if f.at == 2: f.at = 3; push(f.node.left)
        elif f.at == 3: f.at = 4; push(f.node.right)
        else:
            v = f.node.val + f.l + f.r; stack.pop()
            if not stack: return v
            p = stack[-1]          # p.at says where v goes
            if p.at == 3: p.l = v
            else: p.r = v

Two rules make it work. Set at before you push the child, so the frame knows where it is when the child is done. And when you pop, the parent's at tells you whether the value is its l or its r: that is the return address doing its job. Each node takes three loop iterations, so the 7-node tree takes 21, and the list is never deeper than the recursion was (Demo: the same walk with your own stack of frames).

Why the list does not overflow

The call stack has a fixed size: about 8 MB for the main thread on Linux, 512 KB to 1 MB for a Java thread, and Python stops at a depth of 1000 (sys.getrecursionlimit()). The canvas shrinks this to 8 frames. A tree that is a chain 10 nodes deep needs 10, so the 9th call fails with RecursionError (Demo: recursion on a 10-deep chain). The explicit version puts the same 10 frames in a list, which grows until memory runs out, while the real call stack holds just total(root) (Demo: own stack on the chain). Real chains of a million nodes, deep directory trees and long linked lists are where this matters.

The simple case: a stack of nodes

Often you do not need the full frame. If no work waits after a child returns, and the order of the work does not matter, each entry only needs the node:

def total(root):
    stack, s = [root], 0
    while stack:
        node = stack.pop()
        s += node.val
        if node.right: stack.append(node.right)
        if node.left: stack.append(node.left)
    return s

Pushing the right child first means the left one is popped first, so this visits nodes in preorder. On the chain the list never holds more than 1 node (Demo: stack of nodes on the chain). Iterative DFS on a graph is the same pattern.

When to convert

Situation	What to do
Depth is small and known (balanced tree, divide and conquer on n items)	Keep the recursion: log n frames is nothing
Depth can grow with the input (lists, chains, deep graphs, user data)	Use an explicit stack
Nothing waits after the child calls, order does not matter	Stack of nodes (or items)
Work after the call (combine results, postorder)	Stack of frames with a state field like at
Only one call, and it is the last thing done	A plain loop: see tail calls

See also Tail Calls and Tail-Call Optimization (the case where no stack is needed at all), Factorial (the call stack of a simple recursion), Depth-First Search and Plain Recursion vs Memoization vs Tabulation (another way to turn recursion into a loop).

Shunting-yard parses expressions with an explicit operator stack instead of recursion: see Infix to Postfix.

What the page leaves out

The canvas uses a call stack of 8 frames and draws one box per frame; real frames differ in size and also hold saved registers and the frame pointer. It leaves out the None calls (the code checks for a child before calling), raising the limit with sys.setrecursionlimit or a bigger thread stack, generators and trampolines as other ways to avoid deep recursion, and how a compiler lays out frames in machine code.

References

Call stack (Wikipedia)

sys.setrecursionlimit (Python documentation)

Tree traversal: iterative implementations (Wikipedia)