Possibly Pythonic Tail Call Optimization (TCO/TRE)

Ian Kelly ian.g.kelly at gmail.com
Wed Jul 15 16:28:31 CEST 2015


On Tue, Jul 14, 2015 at 11:27 AM, Marko Rauhamaa <marko at pacujo.net> wrote:
> Ian Kelly <ian.g.kelly at gmail.com>:
>
>> On Tue, Jul 14, 2015 at 2:33 AM, Marko Rauhamaa <marko at pacujo.net> wrote:
>>> The programmer shouldn't be controlling tail call optimizations.
>>
>> The programmer controls it regardless.
>>
>>     return foo()  # TCO
>>
>>     result = foo()  # No TCO
>>     return result  # No TCO
>
> Not necessarily. Compile this function with gcc ("gcc -S -O2 atoi.c"):
>
> ========================================================================
> int atoi(const char *str, int n)
> {
>     if (str && *str)
>         n = atoi(str + 1, n * 10 + *str - '0');
>     return n;
> }
> ========================================================================
> (Example modified from <URL: http://stackoverflow.com/questions/34125/wh
> ich-if-any-c-compilers-do-tail-recursion-optimization#220660>.)
>
> You'll see that the generated code is tail-call-optimized.

This can't be done generally, though. What if, instead of a local
variable, the assignment were to a dict item? Even if the dict itself
is a local variable, the assignment can't be optimized away.


More information about the Python-list mailing list