Recursion to iteration

Every recursive function can be rewritten as a loop. Sometimes the loop is simpler. Sometimes it is needed, because the recursion would be deeper than Python allows. The tool that makes it work is a stack that you keep yourself.

When a loop is enough

If a function makes one recursive call and that call is the last thing it does, it is really a loop. The parameters just change on each pass:

def gcd(a, b):                # recursive
    return a if b == 0 else gcd(b, a % b)

def gcd(a, b):                # the same, as a loop
    while b != 0:
        a, b = b, a % b
    return a

If the work happens on the way back up, as in fact, change the order and do the work on the way forward: start a running product at 1 and multiply by 1, 2, …, n.

Memoised recursion as a table

A memoised function (lesson 3) fills in answers for small arguments first, then bigger ones. A loop can fill the same table in the same order, smallest first. This is called working bottom-up:

def fib(n):
    if n < 2:
        return n
    prev, cur = 0, 1                # fib(0), fib(1)
    for _ in range(n - 1):
        prev, cur = cur, prev + cur
    return cur

No recursion, so no depth limit. And because each value needs only the two before it, the table shrinks to two names: O(1) space. The DYNP station is built on this step.

Your own stack

When a function makes several calls, or must come back to finish work, a plain loop is not enough. Use a list as a stack: push what is left to do, and pop the next job off the top. Python’s call stack did exactly this; now you do it, with no depth limit. Step through both versions:

def flatten(x, out):
    for v in x:
        if isinstance(v, list):
            flatten(v, out)
        else:
            out.append(v)

[]

The items are pushed in reverse order so that the first one is popped first. This keeps the same left-to-right order as the recursive version. If the order does not matter, you can skip the reverse.

When to switch

• The depth can grow with the input, as with long linked lists, deep nesting or tall trees. Then use a loop or your own stack.
• The depth stays small, like log n or a short search. Then recursion is fine, and often clearer.
• Speed matters a lot. A Python function call costs more than a loop pass, so a loop can be a few times faster.

Now try RECR-P6, Parcels inside parcels and RECR-P2, Steps on the footbridge.