Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #89755

Re: Python is not bad ;-)

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Python is not bad ;-) Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 09:07 +0200
  Re: Python is not bad ;-) Ben Finney <ben+python@benfinney.id.au> - 2015-04-30 19:10 +1000
    Re: Python is not bad ;-) Marko Rauhamaa <marko@pacujo.net> - 2015-04-30 13:16 +0300
      Re: Python is not bad ;-) Chris Angelico <rosuav@gmail.com> - 2015-04-30 20:52 +1000
      Re: Python is not bad ;-) Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 13:30 +0200
        Re: Python is not bad ;-) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-01 17:03 +1000
          Re: Python is not bad ;-) Cecil Westerhof <Cecil@decebal.nl> - 2015-05-01 09:47 +0200
          Re: Python is not bad ;-) Christian Gollwitzer <auriocus@gmx.de> - 2015-05-01 19:56 +0200
          Re: Python is not bad ;-) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-02 19:44 +1200
          Re: Python is not bad ;-) Cecil Westerhof <Cecil@decebal.nl> - 2015-05-02 10:26 +0200
            Re: Python is not bad ;-) Marko Rauhamaa <marko@pacujo.net> - 2015-05-02 12:10 +0300
              Re: Python is not bad ;-) Chris Angelico <rosuav@gmail.com> - 2015-05-02 19:25 +1000
                Re: Python is not bad ;-) Marko Rauhamaa <marko@pacujo.net> - 2015-05-02 12:58 +0300
                Re: Python is not bad ;-) Dave Angel <davea@davea.name> - 2015-05-02 06:22 -0400
                Re: Python is not bad ;-) Chris Angelico <rosuav@gmail.com> - 2015-05-02 20:42 +1000
                Re: Python is not bad ;-) Christian Gollwitzer <auriocus@gmx.de> - 2015-05-02 13:07 +0200
                Re: Python is not bad ;-) Chris Angelico <rosuav@gmail.com> - 2015-05-02 21:21 +1000
                Re: Python is not bad ;-) Christian Gollwitzer <auriocus@gmx.de> - 2015-05-02 13:32 +0200
                Re: Python is not bad ;-) Marko Rauhamaa <marko@pacujo.net> - 2015-05-02 14:42 +0300
                Re: Python is not bad ;-) Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-02 09:45 -0600
                Re: Python is not bad ;-) Chris Angelico <rosuav@gmail.com> - 2015-05-03 01:55 +1000
                Re: Python is not bad ;-) Joonas Liik <liik.joonas@gmail.com> - 2015-05-02 16:50 +0300
                Re: Python is not bad ;-) Joonas Liik <liik.joonas@gmail.com> - 2015-05-02 18:53 +0300
                Re: Python is not bad ;-) Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-02 11:00 -0600
                Re: Python is not bad ;-) Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-02 11:17 -0600
                Re: Python is not bad ;-) Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-02 18:22 +0100
              Re: Python is not bad ;-) Cecil Westerhof <Cecil@decebal.nl> - 2015-05-02 12:29 +0200
            Re: Python is not bad ;-) Cecil Westerhof <Cecil@decebal.nl> - 2015-05-02 11:33 +0200
              Re: Python is not bad ;-) Dave Angel <davea@davea.name> - 2015-05-02 06:35 -0400
                Re: Python is not bad ;-) Cecil Westerhof <Cecil@decebal.nl> - 2015-05-02 13:12 +0200
              Re: Python is not bad ;-) Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-02 09:31 -0600
      Re: Python is not bad ;-) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-01 15:56 +1000
    Re: Python is not bad ;-) Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 13:10 +0200
  Re: Python is not bad ;-) Michael Torrie <torriem@gmail.com> - 2015-04-30 08:03 -0600
    Re: Python is not bad ;-) Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 18:11 +0200
      Re: Python is not bad ;-) Christian Gollwitzer <auriocus@gmx.de> - 2015-04-30 19:59 +0200
        Re: Python is not bad ;-) Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 22:05 +0200

csiph-web