Possibly Pythonic Tail Call Optimization (TCO/TRE)

Marko Rauhamaa marko at pacujo.net
Tue Jul 14 09:05:46 CEST 2015


Gregory Ewing <greg.ewing at canterbury.ac.nz>:

> Marko Rauhamaa wrote:
>> How about "return"?
>
> How about "goto"? :-)
>
> That's not entirely an unserious suggestion -- if you
> really believe that a "goto with arguments" is a good
> feature for a language to have, you shouldn't be
> afraid to spell it as such.
>
>   def quicksort(array, start, end):
>      midp = partition(array, start, end)
>      if midp <= (start+end)//2:
>         quicksort(array, start, midp)
>         goto quicksort(array, midp+1, end)
>      else:
>         quicksort(array, midp+1, end)
>         goto quicksort(array, start, midp)

This works already now:

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

It might even be tail-call optimized by Python. Only you can't count on
it because the language spec doesn't guarantee it.


Marko


More information about the Python-list mailing list