Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Paul Rubin]

Chris Angelico <rosuav at gmail.com> writes:
> 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.

You partition the array into two parts, one of which has at most N/2
elements.  You push that smaller one onto the stack and recurse, so at
the next recursive level you push at most an N/4 part, then N/8 and so
on.  In that way the total recursion depth is O(log N).  If N=1e6 you
enter 20 levels of recursion which is no big deal.

If you also push the larger part on the stack, it can have size as high
as N-1, so you can end up pushing N-1, N-2, N-3, etc.  If N=1e6 you
overflow the stack when you've barely gotten started.

So it's important in that example that both of the recursive calls
involving the larger partition are both tail calls.  It's fine that the
first call pushes stuff on the stack.  It's vital that the second call
be turned into a goto.