[Python-ideas] Tail recursion elimination

[Terry Reedy]

On 1/18/2014 9:52 AM, 
musicdenotation at gmail.com wrote:

A few notes first:

1) A tail call is a 'top level' call in a return statement.
     return f(*args, **kwds)
A directly recursive call, where f refers to the function with the 
return statement, is a special case.

2) Whether a tail call is directly recursive cannot be determined, in 
Python, at compile time merely by looking at the function definition. If 
'f' is the definition name of the function, an assumption can be made, 
but doing so is a semantic change in the language.

3). 'Tail recursion elimination' has two quite different meanings.

3a. Compile the (in Python, assumed to be) directly recursive function 
as if it had been written with a while loop. This is typically done in 
languages that do not expose while loops. This eliminates the function 
call overhead as well as stack growth. This does nothing for indirect 
recursion through intermediate function calls.

3b. At runtime, make the call but reuse the current stack frame. This is 
easily done (at least in CPython) for all tail calls. But doing so for 
all tail calls will make stack traces pretty useless, as tail calls are 
rather common.  Determining whether the call is recursive, to limit 
stack reuse, takes extra work. Either choice only eliminates stack growth.

Comments on some of you responses to a *subset* of TRE issues.

> On April 22, 2009, Guido van Rossum wrote:
>> First, <the stack trace issue>
...
> Do [while/for] loops have nice stack traces as you mean it?

No, if you want a complete trace, you must add a print statement inside 
the loop. Looping with tail recursion gives you the complete trace for free.

>> Second, <what is fundamental>
...
What is fundamental, besides alternation, is the ability to express an
unbounded amount of repetition, with variation, in a small finite amount 
of code.  I call this computational induction, in analogy to 
mathematical induction. The alternative implemenations include recursion 
and explicit while/for loops. There are also the combinator and fixed 
point approaches.

>> <writing repetition with explicit loops>

> I think the most obvious way to do something is how it is /defined/.

Most recursive definitions are naturally written with body recursion 
rather than tail recursion. A simple example (without input checking) is 
the factorial function.

def fact(n):
   if n: return fact(n-1) * n
   else: return 1

To get TRE, one must re-write in tail-recursive form. (Python default 
arguments actually make this easier than in most languages.)

def fact(N, n=1, result=1):
   if n<N: return fact(n+1, result*(n+1)
   else: return result

I have intentionally written the tail form so it calculates intermediate 
results in the same order, making no assumption that the reduction 
operator is either cummutative or associative. Once the work of 
converting to tail form is done, conversion to while form is trivial and 
easier than the conversion from body to tail recursion.

def fact(N):
   n, result = 1, 1
   while n < N:
     n, result = n+1, result*(n+1)

But in fact, Python has another alternative, for loops.

def fact(N):
   result = 1
   for n in range(2, N):
     result = result * n
   return result

For loops are the proper way to write most collection processing that 
one could write with tail recursion, as it makes use of Python's 
iterator protocol.

def sum(iterable):
   sum = 0
   for n in iterable:
     sum = sum + n
   return sum

To write that with either recursion or while, one must call iter() and 
next() and catch StopIteration oneself. Try it (I have) and see if you 
really think it more natural. Lisp/scheme get away with recursion for 
collection processing because there is only one collection type and 
clever pattern-matching syntax to deconstruct an instance to get one 
element at a time. I personally consider the efficiency of for loops, 
for both programmer and computer, to  be a major reason to not bother 
with TRE.

-- 
Terry Jan Reedy