Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: Throw the cat among the pigeons
Date: Tue, 05 May 2015 16:46:06 -0400
References: <87h9rvm576.fsf@Equus.decebal.nl> <871tixlmp6.fsf@Equus.decebal.nl> <750db03b-e393-43ff-9ccf-5cc050af7324@googlegroups.com> <87zj5jf15q.fsf@Equus.decebal.nl>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: quoted-printable
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
In-Reply-To: <87zj5jf15q.fsf@Equus.decebal.nl>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.140.1430858780.12865.python-list@python.org>
Lines: 119
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:90000

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/mathDeceb=
al.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=20
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=20
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=3D2, res=3D1):
     if i <=3D n:
         return fac_rt(n, i+1, res*i)
     else:
         return res

def fac_iw(n):
     i =3D 2
     res =3D 1
     while i <=3D n:
         i, res =3D i+1, res*i
     return res

for i in (0, 1, 2, 6):
     print(fac(i) =3D=3D fac_rt(i) =3D=3D fac_iw(i))

 >>>
1 1 2 720
True
True
True
True

For collection functions that process each item once, 'for item in=20
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=20
call in one branch of an if-else, are the most common.  Something with=20
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=20
'base_condition' in the original version might not really be the base=20
condition due to a dependence on nonbase1 being false.  This is a=20
generic problem with reordering if-elif statements.

For non-linear (branching) recursion, in which multiple recursive calls=20
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=20
call may not be simple, but it also does not eliminate the possibility=20
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 =E2=80=98tail recursive=E2=80=99 versi=
on was more
> efficient as the iterative version.

In your first thread, what you mislabelled 'tail recursive version' was=20
an iterative while loop version while the 'iterative version' was an=20
iterative for loop version.  In this thread, you just posted timings=20
without code. I will not believe your claim until I see one file that I=20
can run myself with an actual tail recursive function, as above, that=20
beats the equivalent while or for loop version.

--=20
Terry Jan Reedy