Velocity Reviews > Re: Tail recursion to while iteration in 2 easy steps

# Re: Tail recursion to while iteration in 2 easy steps

Terry Reedy
Guest
Posts: n/a

 10-02-2013
On 10/2/2013 8:31 AM, http://www.velocityreviews.com/forums/(E-Mail Removed) 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:

def fact_for(n):
if n < 0 or n != int(n):
raise ValueError('fact input {} is not a count'.format(n))
fac = 1:
for i in range(2, n):
fac *= n

When the input to a function is an iterable instead of n, the iterable
should be part of the for loop source expression. For loops are
integrated with Python's iterator protocol in much the same way that
recursion is integrated with list first:rest pattern matching in some
functional languages. It is true that Python encourages the use of for
loops and for clauses in comprehensions (a functional construct).

5. Conversion of apparent recursion to iteration assumes that the
function really is intended to be recursive. This assumption is the
basis for replacing the recursive call with assignment and an implied
internal goto. The programmer can determine that this semantic change is
correct; the compiler should not assume that. (Because of Python's late
name-binding semantics, recursive *intent* is better expressed in Python
with iterative syntax than function call syntax. )

--
Terry Jan Reedy

88888 Dihedral
Guest
Posts: n/a

 10-04-2013
On Thursday, October 3, 2013 5:33:27 AM UTC+8, Terry Reedy wrote:
> On 10/2/2013 8:31 AM, (E-Mail Removed) 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.