New tail recursion decorator

Tim N. van der Leeuw tim.leeuwvander at nl.unisys.com
Fri May 12 14:27:32 CEST 2006


[...]
> >
> I'm not convinced by this. You have to recognise that the function is using
> tail recursion, and then you have to modify the code to know that it is
> using tail recursion. This is not always trivial. For example, the given
> example is:
>
> @tail_recursion
> def factorial(n, acc=1):
>     "calculate a factorial"
>     if n == 0:
>        return acc
>     res = factorial(n-1, n*acc)
>     return res
>
> but a more common way to write the function would be:
>
> @tail_recursion
> def factorial(n):
>     "calculate a factorial"
>     if n == 0:
>        return 1
>     return n * factorial(n-1)
>
> which won't work because it isn't actually tail recursion, but it looks
> sufficiently close to tail recursion that it would probably mislead a lot
> of people into expecting it will work. If you are going to have to rewrite
> functions in a stilted manner, and they use simple tail recursion, then why
> not just factor out the tail recursion in the first place.
>
[...]

Hi Duncan,

I don't know why it wouldn't work this way, or why it isn't
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.

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


Cheers,

--Tim




More information about the Python-list mailing list