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