Python Tail Recursion "Hack" using While Loop

Question

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?

That's how tail call optimization is translated to imperative code in general, yes. — lambda.xy.x
– lambda.xy.x, Commented Sep 7, 2020 at 20:04
strictly speaking tail_exp_2 does not use recursion... so there is no real tail call optimization. — hiro protagonist
– hiro protagonist, Commented Sep 7, 2020 at 20:04
@hiroprotagonist I would tend to agree, yet I've seen this approach touted as a way to do tail call optimization in Python. So if this is not recursion, what is it exactly, and what is its relationship to recursion? — Robin Andrews
– Robin Andrews, Commented Sep 7, 2020 at 20:08
This is neither Python-specific nor is it "tail call optimization" -- you're simply converting a recursive algorithm into an iterative one by hand, which you can always do in general. TCO is what you call it when the compiler does that conversion for you automatically, since it's fairly simple to do in the specific case of tail recursion. There are no "gotchas" involved as long as you do the conversion correctly. — tzaman
– tzaman, Commented Sep 7, 2020 at 20:09
It is a loop - in general recursion needs to build up a call stack in a loop that gets unwound on returns. In case of TCO, the intermediary elements of the stack don't matter and you can just overwrite the variables. — lambda.xy.x
– lambda.xy.x, Commented Sep 7, 2020 at 20:10

Blckknght · Accepted Answer · 2020-09-07 21:33:19Z

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.

Collectives™ on Stack Overflow

Python Tail Recursion "Hack" using While Loop

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related