Tail recursion to while iteration in 2 easy steps

[Terry Reedy]

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:

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