CODEWITHSUNDEEP
pythonrecursiontail-recursion
Robin Andrews
Robin Andrews

Reputation: 3804

Python Tail Recursion "Hack" using While Loop

I've seen a few examples of getting Python to do tail call optimization by using a while True loop. E.g.

def tail_exp(base, exponent, acc=1):
    if exponent == 0:
        return acc
    return tail_exp(base, exponent - 1, acc * base)

becomes


def tail_exp_2(base, exponent, acc=1):
    while True:
        if exponent == 0:
            return acc
        exponent, acc = exponent - 1, acc * base

I'm curious to know if this technique is applicable to all/most recursive algorithms in Python, and if there are any downsides or "gotchas" to look out for when optimizing recursive algorithms in this way?

Upvotes: 3

Views: 1792

Answers (1)

Blckknght
Blckknght

Reputation: 104792

Any recursive algorithm can be replaced by an iterative one. However, some examples will require an additional stack be added to the code, to manage state that is handled by the recursive calls in the original form. With tail recursion, there is no state to be managed, so no separate stack is needed.

Some programming languages take advantage of that fact and design their compilers to optimize out tail calls in recursive code, producing machine code that is equivalent to a loop. Python does not do tail call optimization, so this isn't really relevant to your question. Rewriting code by hand is not tail call optimization, it's just a particular sort of refactoring.

There are a few reasons Python chooses not to do tail call optimization. It's not because it's impossible. Python code is compiled into byte code, so at least theoretically there's an opportunity to translate a recursive call into a loop if that was desired by the developers (in practice it's a little more complicated, since Python variable names are dynamic, you can't necessarily tell if a function name refers to what you expect it to at runtime, a fact use by techniques like monkeypatching). However, the biggest problem with tail call optimization is that it generally overwrites useful debugging information that would usually be preserved by a call stack, like exactly how deep in the recursion you are and the exact state of those previous function calls. The Python developers have decided that they prefer the simplicity and debuggability of normal recursion over performance benefits of tail call optimization, even when the latter is possible.

If you want to rewrite an algorithm from a recursive implementation into an iterative one, you can always do so. In some cases, though, it may get a lot more complicated. Recursive implementations of some algorithms can be a lot shorter, simpler, and easier to reason about, even though iterative equivalents may be faster (and won't hit the recursion limit for large inputs). Converting tail calls into a loop is usually quite simple though. The complicated cases are generally not amenable to tail call optimization either, since they're doing complicated stuff with the values returned by their recursion.

Upvotes: 4

Related Questions