New tail recursion decorator

Michele Simionato michele.simionato at gmail.com
Fri May 12 14:40:56 CEST 2006


Tim N. van der Leeuw wrote:
>
> I don't know why it wouldn't work this way, or why it isn't
> tail-recursion?

>From the google page do "define: tail recursion"

> I tried the tail_recursion decorator from the cookbook-recipe with both
> definitions of factorial, and I tried both definitions of the factorial
> function with and without tail_recursion decorator.
> In all four cases I get the same results, so it does work with both
> definitions of factorial(), even if (according to you) the second
> definition is not proper tail-recursion.

For me factorial(1001) with the second definition does not work, I get
the recursion limit (which is what I expect). I suppose the recursion
limit is higher on your system, but definitely you should reach it at
some point with the non tail-recursive version of factorial.

> Using the tail-recursion decorator (the version that does not inspect
> the stackframes) I get a small performance-increase over using the
> factorial-function undecorated.
> However, calculating factorial(1000) with the factorial-function as
> defined in the cookbook-recipe is much much faster than calculating the
> same factorial(1000) with the factorial-function you gave!
> I cannot yet explain why the first function has so much better
> performance than the second function  - about a factor 10 difference,
> in both python2.4.3 and python 2.5a2

It is because the decorator is doing is job (converting a long
recursion in a loop)
only with the first function, which is properly tail recursive. Just as
Duncan said.

             Michele Simionato




More information about the Python-list mailing list