Tail recursion to while iteration in 2 easy steps
88888 Dihedral
dihedral88888 at gmail.com
Fri Oct 4 05:13:07 EDT 2013
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.
More information about the Python-list
mailing list