Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Paul Rubin]

Chris Angelico <rosuav at gmail.com> writes:
> I'm not sure why the transition to another state has to be recursive.

It's not recursive: it's more like a goto with arguments, and a tail
call expresses it nicely.

> Maybe this is something where previous experience makes you more
> comfortable with a particular style, which will mean that functional
> idioms will never feel more comfortable to me than iterative ones do,
> and vice versa for you. If that's the case, then I'll stick with
> Python and Pike, and you can happily use Lisp and Haskell, and neither
> of us need be a problem to the other. 

Do you also use explicit loops instead of list comprehensions?  They are
another nice functional idiom adapted into Python.

> That's why I said "example please?". My experience has not a single
> time come across this. If you want to make an assertion that iterative
> code requires equivalent warping to tail-recursive code, I want to see
> an example of it. Is that difficult?

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 ;-).