Throw the cat among the pigeons

[Terry Reedy]

On 5/5/2015 12:18 PM, Cecil Westerhof wrote:
> Op Tuesday 5 May 2015 17:47 CEST schreef Paul Moore:
>
>> On Sunday, 3 May 2015 16:23:59 UTC+1, Cecil Westerhof  wrote:
>>>> By the way: I think that even if the recursion does not go further
>>>> as 500, it is still a good idea to use tail recursion. Why use
>>>> stack space when it is not necessary?
>>>
>>> I pushed the example to GitHub:
>>> https://github.com/CecilWesterhof/PythonLibrary/blob/master/mathDecebal.py
>>
>> You already know this, as your code shows, but tail call recursion
>> elimination is only possible when you have a *direct* tail call (one

An 'indirect tail call' would not be a tail call.

>> with the result of the tail call returned immediately to the
>> caller). Even the standard trivial factorial example doesn't have a
>> direct tail call,  without rewriting to use an accumulator variable.
>> Which is a non-intuitive transformation to anyone who's not familiar
>> with recursive functional languages and their idioms.
>>
>> If you're rewriting your recursive function *anyway*, it's not that
>> much harder in many (most?) cases to rewrite it iteratively.

For count functions, the main change between tail recursion and while 
iteration is replacing 'if' with 'while' and converting the tail call to 
assignment.  (One may have to reverse the if-else first to put the tail 
call in the if branch.)

from math import factorial as fac
print(fac(0), fac(1), fac(2), fac(6))

def fac_rt(n, i=2, res=1):
     if i <= n:
         return fac_rt(n, i+1, res*i)
     else:
         return res

def fac_iw(n):
     i = 2
     res = 1
     while i <= n:
         i, res = i+1, res*i
     return res

for i in (0, 1, 2, 6):
     print(fac(i) == fac_rt(i) == fac_iw(i))

 >>>
1 1 2 720
True
True
True
True

For collection functions that process each item once, 'for item in 
collection: ...' is nearly always easier to write in the first place.

>> An example of a function that naturally uses direct tail call
>> recursion, but which doesn't have a simple iterative rewrite, would
>> be more compelling.

Simple, easily converted functions like the above, with one recursive 
call in one branch of an if-else, are the most common.  Something with 
multiple mutually exclusive tail calls, like the following

def f_rt1(*args):
   if nonbase1:
     return f(*revised-args1)
   elif base_condition:
     return base(args)
   else:
     return f(*revised-args2)

must be converted to if-else with all tail calls in the if branch.

def f_rt2(*args):
   if not base_condition:
     if nonbase1:
       return f(*revised-args1)
     else:
       return f(*revised-args2)
   else:
     return base(args)

Conversion would then be simple.  The complication is that the 
'base_condition' in the original version might not really be the base 
condition due to a dependence on nonbase1 being false.  This is a 
generic problem with reordering if-elif statements.

For non-linear (branching) recursion, in which multiple recursive calls 
may be made for one function call, the last recursive call may be a tail 
call.  An example is in-place quick sort.  Eliminating just the tail 
call may not be simple, but it also does not eliminate the possibility 
of blowing the call stack.  To do that, one must eliminate all recursive 
calls by adding explicit stacks.

> Well, I did not write many tail recursive functions. But what surprised
> me was that for large values the ‘tail recursive’ version was more
> efficient as the iterative version.

In your first thread, what you mislabelled 'tail recursive version' was 
an iterative while loop version while the 'iterative version' was an 
iterative for loop version.  In this thread, you just posted timings 
without code. I will not believe your claim until I see one file that I 
can run myself with an actual tail recursive function, as above, that 
beats the equivalent while or for loop version.

-- 
Terry Jan Reedy