Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Chris Angelico]

On Tue, Jul 14, 2015 at 3:15 PM, Paul Rubin <no.email at nospam.invalid> wrote:
> It's difficult given how subjective the concept of warping is.  What's
> straightforward to someone else sounds likely to look warped to you and
> vice versa.  But how does this look:
>
>   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)
>
> I assume you know how quicksort and its partition step work.  The idea
> is you partition the array around the pivot element (midp is the index
> of that element), then recursively sort the two partitions, doing the
> smaller partition as a recursive call and the larger one as a tail call,
> so that you use O(log n) stack depth instead of potentially O(n).
>
> So the idea is that the second quicksort call in each branch of the if
> is a tail call.  Yes you could code that as a loop but from my
> perspective the way I wrote it above looks more natural.
>
> Of course it's also possible that I've totally derped this and the
> example is no good for some reason I've missed so far ;-).

That's a prime example of recursion... but not of recursion that can
be tail-call optimized into iteration. It's an example of forking
recursion, where one call can result in multiple calls (same with tree
traversal); it calls itself to sort the first part and the last part,
and while you might be able to turn the second call into a goto, you
still need stack space to maintain the first 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.

(Also, side point: Python can't actually optimize the above function,
because it actually means "call quicksort, then discard its return
value and return None". A true tail call has to return the result of
the recursive call, and Python lacks a way to say "this function will
always return None". But that's trivial.)

ChrisA