Explain To Me What The Big Deal With Tail Call Optimization Is And Why Python Needs It

So apparently, there's been a big brouhaha over whether or not Python needs tail call optimization. This came to a head when someone shipped Guido a copy of SICP because he didn't

Solution 1:

Personally, I put great value on tail call optimization; but mainly because it makes recursion as efficient as iteration (or makes iteration a subset of recursion). In minimalistic languages you get huge expressive power without sacrificing performance.

In a 'practical' language (like Python), OTOH, you usually have a lot of other constructions for almost every situation imaginable, so it's less critical. It is always a good thing to have, to allow for unforeseen situations, of course.

Personally, I put great value on tail call optimization; but mainly because it makes recursion as efficient as iteration (or makes iteration a subset of recursion). In minimalistic languages you get huge expressive power without sacrificing performance.

In a 'practical' language (like Python), OTOH, you usually have a lot of other constructions for almost every situation imaginable, so it's less critical. It is always a good thing to have, to allow for unforeseen situations, of course.

Solution 2:

If you intensely want to use recursion for things that might alternatively be expressed as loops, then "tail call optimization" is really a must. However, Guido, Python's Benevolent Dictator For Life (BDFL), strongly believes in loops being expressed as loops -- so he's not going to special-case tail calls (sacrificing stack-trace dumps and debugging regularity).

Solution 3:

Tail call optimization makes it easier to write recursive functions without worrying about a stack overflow:

def fac(n, result=1):
        if n >1:
                return fac(n -1, n *result)
        returnresult

Without tail call optimization, calling this with a big number could overflow the stack.

Solution 4:

Guido recognized in a follow up post that TCO allowed a cleaner the implementation of state machine as a collection of functions recursively calling each other. However in the same post he proposes an alternative equally cleaner solution without TCO.