Path: csiph.com!usenet.pasdenom.info!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <5544A55C.2070504@davea.name>
References: <87mw1q9jqw.fsf@Equus.decebal.nl> <mailman.121.1430385051.3680.python-list@python.org> <87383hj4zj.fsf@elektro.pacujo.net> <87d22lx38x.fsf@Equus.decebal.nl> <55432557$0$12994$c3e8da3$5496439d@news.astraweb.com> <87383fo062.fsf@Equus.decebal.nl> <87egmzl4yr.fsf@elektro.pacujo.net> <mailman.4.1430558719.12865.python-list@python.org> <87a8xnl2r6.fsf@elektro.pacujo.net> <5544A55C.2070504@davea.name>
Date: Sat, 2 May 2015 20:42:14 +1000
Subject: Re: Python is not bad ;-)
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.7.1430563337.12865.python-list@python.org>
Lines: 57
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:89759

On Sat, May 2, 2015 at 8:22 PM, Dave Angel <davea@davea.name> wrote:
> On 05/02/2015 05:58 AM, Marko Rauhamaa wrote:
>>
>> Chris Angelico <rosuav@gmail.com>:
>>
>>> Guido is against anything that disrupts tracebacks, and optimizing
>>> tail recursion while maintaining traceback integrity is rather harder.
>>
>>
>> Tail recursion could be suppressed during debugging. Optimized code can
>> play all kinds of non-obvious tricks with the execution frame.
>>
>>> In the situations where it really is simple, you can always make the
>>> change in your own code anyway. Often, the process of converting
>>> recursion into tail recursion warps the code to the point where it's
>>> abusing recursion to implement iteration anyway, so just make it
>>> iterative.
>>
>>
>> While you shouldn't actively replace Python iteration with recursion, I
>> strongly disagree that naturally occurring tail recursion is abuse or
>> should be avoided in any manner.
>>
>
> When you strongly disagree, make sure you're disagreeing with what Chris
> actually said.  The key phrase in his message was
>     "converting recursion into tail recursion"
>
> NOT  "converting iteration into recursion"
> and NOT "naturally occurring tail recursion"

Indeed. I'll clarify my statement.

When a function needs to do further actions after the tail call, the
usual solution is to carry the information through parameters.

def stupid_sum_iter(x):
    """Calculate sum(range(x+1))"""
    tot = 0
    while x:
        tot += x
        x -= 1
    return tot

def stupid_sum_recur(x):
    return x and x + stupid_sum_recur(x - 1)

def stupid_sum_tail_recur(x, tot=0):
    if not x: return tot
    return stupid_sum_tail_recur(x - 1, tot + x)

Converting the recursive form into optimizable tail recursion requires
an accumulator parameter, which means it's virtually the same as the
iterative version. Naturally-occurring tail recursion does exist, but
it's far from all cases of recursion.

ChrisA