Tail recursion to while iteration in 2 easy steps

[88888 Dihedral]

On Thursday, October 3, 2013 5:33:27 AM UTC+8, Terry Reedy wrote:
> On 10/2/2013 8:31 AM, random832 at 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.