Possibly Pythonic Tail Call Optimization (TCO/TRE)
Terry Reedy
tjreedy at udel.edu
Tue Jul 14 20:23:27 EDT 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
body should start with 'if not terminal(start, end):' where terminal is
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
More information about the Python-list
mailing list