Explicit stacks and the recursion limit

The same traversal can be written iteratively with an explicit stack — a last-in, first-out pile of work you manage yourself. You pop a node to process it and push its children to be processed later:

def tree_sum_iter(root):
    total, stack = 0, [root]
    while stack:
        node = stack.pop()               # take the most recently added
        total += node["val"]
        stack.extend(node["children"])   # add its children to the pile
    return total

Recursion uses Python's own call stack to remember pending work; the explicit version just does that bookkeeping by hand. A stack always processes the most recently added item first — that's what "last in, first out" means.

The Python-specific catch is tail calls. Some languages optimise a function whose last act is to call itself, reusing one stack frame; CPython does not. So deep recursion piles up frames until it hits the recursion limit (around 1000) and crashes with a RecursionError.

When depth could be large, rewrite the recursion as an accumulator plus a loop, which runs in constant stack space:

def factorial(n, acc=1):
    while n > 1:          # the loop replaces the would-be tail call
        acc *= n
        n -= 1
    return acc

Reach for recursion on shallow, naturally nested structures; reach for the explicit stack or loop when depth could be large.
leads into “Functions as values; writing a decorator”.*