# Possibly Pythonic Tail Call Optimization (TCO/TRE)

Terry Reedy tjreedy at udel.edu
Wed Jul 15 02:23:27 CEST 2015

```On 7/14/2015 1:15 AM, Paul Rubin wrote:

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

Thank you for the example.  It I have ever seen how to minimize the max
stack needed for first calls, I have forgotten.  First some comment:
1. There is no terminal condition, so the above will loop forever. The
the actual expression.  I did not write it because it depends on whether
'end' is the highest index or one past it.
2. There are no tail calls (call followed by return), so a tail-call
optimizer will not optimize this.  A recur() function might be able to.
3. Mutation is anathema to functional programming, so a functional
programmer would never write and version of this, at least not without
holding his nose.

The tail-like calls in each branch can be avoided with assignment and
gobacks.  In Python, we go-back with while loops. (IE, 'while' = 'label'
+ 'if' + 'goto'.)  With minimal change to the above, we get (untested)

def quicksort(array, start, end):
while not terminal(start, end):
midp = partition(array, start, end)
if midp <= (start+end) // 2:
quicksort(array, start, midp)
start = midp+1
else:
quicksort(array, midp+1, end)
end = midp

I can understand that someone might prefer to break the symmetry of the
paired calls by wrapping the second with recur() (assuming that such a
function is sensibly feasible on *all* implementations).  In the other
hand, I prefer the reduced-noise explicit assignment that highlights the
one parameter that gets rebound.

--
Terry Jan Reedy

```