Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #55382 > unrolled thread

Re: Tail recursion to while iteration in 2 easy steps

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 17:33 -0400
    Re: Tail recursion to while iteration in 2 easy steps 88888 Dihedral <dihedral88888@gmail.com> - 2013-10-04 02:13 -0700

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

On 10/2/2013 8:31 AM, random832@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:

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

[toc] | [next] | [standalone]

#55458

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web