Converting Recursion to Iteration

Recursive code is often concise, but every call consumes stack space. There are two common ways to convert it to iteration.

For tail-recursive functions, move intermediate state into accumulator parameters. Factorial, for example, can carry the current product and repeatedly update it in a loop:

def factorial(n):
    result = 1
    while n > 1:
        result *= n
        n -= 1
    return result

General recursion requires preserving work that would otherwise live in call frames. Use an explicit stack, push the pending subproblems, and pop them until none remain. An iterative quicksort can store (left, right) ranges, partition one range, then push the two remaining ranges.

The key is to identify what each recursive frame remembers: arguments, local state, and what must happen after a child call returns. Tail calls need only updated state; non-tail calls need an explicit representation of the continuation. Iteration avoids call-stack limits, although an explicit stack may still use comparable memory.

Originally published on SegmentFault.