On Thursday, October 3, 2013 5:33:27 AM UTC+8, Terry Reedy wrote: > On 10/2/2013 8:31 AM, random...@fastmail.us wrote: > > > On Tue, Oct 1, 2013, at 17:30, Terry Reedy wrote: > > >> Part of the reason that Python does not do tail call optimization is > > >> that turning tail recursion into while iteration is almost trivial, once > > >> you know the secret of the two easy steps. Here it is. > > > > > > That should be a reason it _does_ do it - saying people should rewrite > > > their functions with loops means declaring that Python is not really a > > > multi-paradigm programming language but rather rejects functional > > > programming styles in favor of imperative ones. > > > > It is true that Python does not encourage the particular functional > > style that is encouraged by auto optimization of tail recursion. A > > different functional style would often use reduce (or fold) instead. > > > > Some other points I left out in a post of medium length yet brief for > > the topic. > > > > 1. If one starts with body recursion, as is typical, one must consider > > commutativity (possibly associativity) of the 'inner' operator in any > > conversion. > > > > 2. Instead of converting to tail recursion, one might convert to while > > iteration directly. > > > > 3. One often 'polishes' the while form in a way that cannot be done > > automatically. > > > > 4. While loops are actually rare in idiomatic Python code. In Python, > > for loops are the standard way to linearly process a collection. The > > final version I gave for a factorial while loop, > > > > def fact_while(n): > > if n < 0 or n != int(n): > > raise ValueError('fact input {} is not a count'.format(n)) > > fac = 1 > > while n > 1: > > fac *= n > > n -= 1 > > return fac > > > > should better be written with a for loop: >
As I pointed out before, an accelerated version without the limit of the stack depth for computing facotrials can be obtained by storing a list of products of primes first. Of course integer divisions are required to transform the to stack depth problem into the size of the 32-64 bit heap space. -- https://mail.python.org/mailman/listinfo/python-list