Op Friday 1 May 2015 09:03 CEST schreef Steven D'Aprano:
> On Thu, 30 Apr 2015 09:30 pm, Cecil Westerhof wrote:
>
>> Tail recursion would nice to have also.
>
> People coming from functional languages like Lisp and Haskell often
> say that, but how many recursive algorithms naturally take a
> tail-call form? Not that many.
One example:
def factorial(x, y = 1):
return y if x == 1 else factorial(x - 1, x * y)
def factorial_iterative(x):
result = 1
for i in range(2, x + 1):
result *= i
return result
Executing factorial(985) 100.000 times takes 54 seconds.
While executing factorial_iterative(985) takes 34 seconds.
Also you can not call factorial with a value that is much bigger
because of recursion depth. You can call factorial_iterative with
1.000.000.
I made also a version that simulates tail recursion:
def factorial_tail_recursion(x):
y = 1
while True:
if x == 1:
return y
y *= x
x -= 1
This is that a lot less efficient as the iterative version. It takes 43
seconds. But it is a lot better as the normal recursive version: about
25%. The iterative version is about 25% more efficient as the tail
recursion version.
With larger values it decreases. Calculating onetime for 5.000.000
takes 117 and 131 seconds. Just 10% faster.
That is mostly because the tail recursion version starts multiplying
at the high end. I wrote a second version:
def factorial_tail_recursion2(x):
y = 1
z = 1
while True:
if x == z:
return y
y *= z
z += 1
This has almost the performance of the iterative version: 34 and 121
seconds.
So I made a new recursive version:
def factorial_recursive(x, y = 1, z = 1):
return y if x == z else factorial_recursive(x, x * y, z + 1)
But this take almost the same tame as the other. Probably the
recursive calls are more important as the multiplications.
I find factorial a lot cleaner code as factorial_iterative, so here
tail recursion would be beneficial.
--
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof
--
https://mail.python.org/mailman/listinfo/python-list
