Path: csiph.com!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <53903f1c-a740-4508-9d24-0b0bec9ad339@googlegroups.com>
References: <53903f1c-a740-4508-9d24-0b0bec9ad339@googlegroups.com>
Date: Thu, 6 Aug 2015 01:51:57 +1000
Subject: Re: Is this an example of tail recursion?
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.1241.1438789920.3674.python-list@python.org>
Lines: 125
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:95024

On Thu, Aug 6, 2015 at 1:13 AM,  <jennyfurtado2@gmail.com> wrote:
> I am trying to learn differences between tail recursion and non tail recursion.

Tail recursion is where you do exactly this:

    return some_function(...)

Absolutely nothing is allowed to happen around or after that function,
and that also means you can't do that inside a try/except/finally
block, nor a with block, etc, etc, etc. It has to be nothing more than
a function call, and you return the exact result of that call.

> Is the following recursive code tail recursive?
> If it is not how to convert it to tail recursion?
> If it is how to convert it to non tail recursion?
>
>    def __init__(self):
>        self.dpw = 0

Not tail recursive - not recursive - doesn't call anything. Trivial case. :)

>    def soldiersVsDefenders(self,soldiers,defenders):
>        # soldiers win
>        if defenders <=0:
>           return 0
>        # castle/defenders win
>        if soldiers <= 0:
>           return self.INFINITY

In these cases, equally trivial - not recursive in any form.

>        # do another round of fighting
>        # 1. Soldiers kill as many defenders
>        defendersLeft = defenders - soldiers
>        # 2. defendersLeft kill as many soldiers
>        soldiersLeft = soldiers - defendersLeft

(Interesting that the attacking soldiers get the first strike.)

>        return 1 + self.soldiersVsDefenders(soldiersLeft,defendersLeft)

This is NOT tail recursion, because you add 1 at the end of it. The
way to make it tail recursive would be to add another argument to the
function, which it would keep adding to; whenever it returns, you
would add the accumulator to the return value:

def soldiersVsDefenders(self,soldiers,defenders, accum=0):
    if defenders <= 0:
        return 0 + accum
    if soldiers <= 0:
        return self.INFINITY + accum
    # other code goes here
    return self.soldiersVsDefenders(soldiersLeft,defendersLeft,1+accum)

Now it's tail recursive. If this looks ugly, it's because it is; tail
recursion often isn't worth the effort.

Note that, as far as Python's concerned, this is a tail call, but
isn't necessarily *recursion* (which implies that you somehow know
you're calling the same function). If someone subclasses your code and
overrides this method, your code will call the subclass's version - if
the subclass calls through to super(), you'll end up with mutual
recursion, but still not a simple case of tail recursion. However, you
could choose to ignore this possibility and manually convert this into
iteration:

def soldiersVsDefenders(self,soldiers,defenders):
    rounds = 0
    while soldiers and defenders:
        # do another round of fighting
        # 1. Soldiers kill as many defenders
        defendersLeft = defenders - soldiers
        # 2. defendersLeft kill as many soldiers
        soldiersLeft = soldiers - defendersLeft
        rounds += 1
    if defenders <= 0:
        return rounds
    return self.INFINITY + rounds

How's that look? Better? Worse?

On to the next function.

>    def oneWave(self,soldiers,defenders,castleHits):
>        # castle is dead, let soldiers play against defenders
>        if castleHits <= 0:
>            defendersLeft = defenders - self.dpw
>            return self.soldiersVsDefenders(soldiers,defendersLeft)

This is a tail call. It's not tail *recursion* because you're calling
a completely different function, but you are indeed calling another
function and directly returning its return value.

>        mini = self.INFINITY
>        for i in range(0,soldiers):
>            if i > defenders:
>                 break
>            soldiersLeft = soldiers - (defenders -i)
>            defendersLeft = defenders - i + self.dpw
>            castleHitsLeft = castleHits - (soldiers -i)
>            mini = min(mini,1 + self.oneWave(soldiersLeft,defendersLeft,castleHitsLeft))
>        return mini

Not sure what the point of all this is, but sure. This clearly isn't
tail recursion, though, as it's doing a whole lot of other work after
the recursive call. Having a loop and recursion like this is pretty
scary, but in terms of "is this or isn't this tail recursive", it's
pretty clear.

>    def playGame(self,soldiers,castleHits,defendersPerWave):
>        self.dpw = defendersPerWave
>        numWaves = self.oneWave(soldiers,0,castleHits)
>        if numWaves >= self.INFINITY:
>           return -1
>        else:
>           return numWaves

And this is, again, no tail call. If the trap for INFINITY becoming -1
were inside oneWave(), then this could be turned into a tail call, but
as it is, there's more work to be done after the other function
returns, so it's not a tail call.

Hope that helps!

ChrisA