Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!newsfeed.fsmpi.rwth-aachen.de!newsfeed.straub-nv.de!newsfeed.pionier.net.pl!feed.xsnews.nl!border03.ams.xsnews.nl!feeder03.ams.xsnews.nl!abp001.ams.xsnews.nl!frontend-F09-14.ams.news.kpn.nl
From: Cecil Westerhof <Cecil@decebal.nl>
Newsgroups: comp.lang.python
Subject: Re: Python is not bad ;-)
Organization: Decebal Computing
References: <87mw1q9jqw.fsf@Equus.decebal.nl> <mailman.121.1430385051.3680.python-list@python.org> <87383hj4zj.fsf@elektro.pacujo.net> <87d22lx38x.fsf@Equus.decebal.nl> <55432557$0$12994$c3e8da3$5496439d@news.astraweb.com> <87383fo062.fsf@Equus.decebal.nl>
X-Face: "(y8cC@tg_12{">GF'UXTW]FHI2wMiZNrnf'1EFQ&O#$m:f#O7+7}kR<J%a^F2lh4[N~Yz4 nSp#c+aQo1b5=?HcNEkQ7QzF<])O3X4MDL/AYjys&*mt>,v+Pti8=Vi/Z"g^?b"E
X-Homepage: http://www.decebal.nl/
Date: Sat, 02 May 2015 11:33:56 +0200
Message-ID: <87twvvmigr.fsf@Equus.decebal.nl>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)
Cancel-Lock: sha1:6h1b1GyBvy62AGYgTQw6qZ64r/c=
MIME-Version: 1.0
Content-Type: text/plain
Lines: 69
NNTP-Posting-Host: 81.207.62.244
X-Trace: 1430559890 news.kpn.nl 25007 81.207.62.244@kpn/81.207.62.244:36702
Xref: csiph.com comp.lang.python:89755

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