Op Saturday 2 May 2015 10:26 CEST schreef Cecil Westerhof: > 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)
Stupid me 'x == z' should be 'z > x' -- Cecil Westerhof Senior Software Engineer LinkedIn: http://www.linkedin.com/in/cecilwesterhof -- https://mail.python.org/mailman/listinfo/python-list
