Why does a naive explicit-stack rewrite lose the work a recursion does after its recursive calls?

## The part of the frame the rewrite drops A frame holds three things: the parameter values for this invocation, its local variables, and a **return address** — where in the body to carry on when the call returns. For a recursion that does nothing after its call, the return address is dead weight. For a recursion that aggregates, it is the whole point. Take a catalogue where every category must end up with its own rolled-up subtotal: a category's total is its own stock plus the totals of each sub-category. The recursion writes itself — recurse on each child, then add the returned values. That addition happens **after** the calls, at the return address. A rewrite that only pushes children models the descent perfectly and models the return not at all: a node is popped once, processed once, and never seen again. There is no moment at which its children are known to be finished. ## Why the loss is easy to miss If the only output is one global total, the descent-only rewrite still gives the right number. Addition into a single accumulator is order-independent and every node is visited exactly once, so the answer matches. Everything that needs the *structure* of the aggregation breaks: - per-category subtotals written back onto each node; - the deepest path in the tree, or the height of each subtree; - a flag like "this category and everything under it is out of stock"; - releasing or unwinding something the descent acquired; - any decision a parent makes conditioned on what its children returned. A passing total is therefore not evidence the rewrite is correct. ## Encoding the resume point The common technique is a phase tag on each stack entry. Popping a node in the `enter` phase means "I have not descended yet": push the same node back tagged `exit`, then push its children tagged `enter`. Because the children land above the parent's `exit` entry, every one of them is fully processed before that entry is popped — and when it is, the post-call work runs with all child results in hand. ``` stack = empty push(stack, (root, "enter")) sums = empty map while stack is not empty: (node, phase) = pop(stack) if phase == "enter": push(stack, (node, "exit")) for i in length(node.children)-1 downto 0: push(stack, (node.children[i], "enter")) else: s = node.stock for i in 0..length(node.children)-1: s = s + sums[node.children[i]] sums[node] = s return sums[root] ``` Each node is pushed twice and popped twice, so the work is still linear in the number of nodes. The tag is doing exactly what the return address did: telling the loop which half of the body to run. Notice the two orderings that both have to be right — the `exit` entry must go on *before* the children, and the children go on in reverse so they are explored in their natural order. ## The alternatives, and what they cost **A separate result stack.** Push results as subtrees complete and have each parent pop as many as it has children. Compact, and completely opaque to the next reader, because the correspondence between nodes and results is implicit in the counts. **An unfinished-children counter.** Give each node a count, decrement it when a child finishes, and run the parent's post-work when it reaches zero. This scales naturally to more than two phases, but it means mutating nodes or maintaining a side table. **Push a resume index instead of a phase.** Rather than two phases, store "I am between child 2 and child 3", which is the general case — it is literally an instruction pointer for the frame, and it is what you end up with when the body interleaves work between the calls rather than only after them. All three are the same admission: to remove the call stack you must reproduce what it stored, and the resume point is the piece people forget. ## When it is worth writing It is worth it when depth is genuinely unbounded by the data and the aggregation must still happen — a supplier-provided catalogue with no depth guarantee, an import path where a single bad tree must not take the process down. It is not worth it for a tree whose depth is bounded by a handful of levels, where you have traded four lines that read like the definition of the problem for twenty lines of hand-managed control flow that the next person has to simulate mentally to trust. "Any recursion converts to a loop" is true; "the loop version is simpler" is the part that is not.