Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Marko Rauhamaa]

Chris Angelico <rosuav at gmail.com>:

>>   def quicksort(array, start, end):
>>      midp = partition(array, start, end)
>>      if midp <= (start+end)//2:
>>         quicksort(array, start, midp)
>>         quicksort(array, midp+1, end)
>>      else:
>>         quicksort(array, midp+1, end)
>>         quicksort(array, start, midp)
> [...]
> That's a prime example of recursion... but not of recursion that can
> be tail-call optimized into iteration.

Of course it can. The 2nd and 4th calls to quicksort can be trivially
tail-call-optimized.

Tail-call optimization has nothing to do with converting algorithms into
iterations. It's a prosaic trick of dropping an unneeded stack frame
before making a function call.

> The claim that TCO means you don't need stack space for all those
> levels of recursion doesn't work if you still need stack space for all
> those levels of recursion *before* you get to the tail call.

Nobody is making that claim.

What you are questioning is what tail-call optimization would buy you in
practice. Not much. The few times you run into a stack overflow, you can
refactor your code pretty easily. However, when you have to do that, it
feels a bit silly.


Marko