Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #95024

Re: Is this an example of tail recursion?

Show key headers only | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Is this an example of tail recursion? jennyfurtado2@gmail.com - 2015-08-05 08:13 -0700
  Re: Is this an example of tail recursion? Rustom Mody <rustompmody@gmail.com> - 2015-08-05 08:21 -0700
    Re: Is this an example of tail recursion? jennyfurtado2@gmail.com - 2015-08-05 08:37 -0700
      Re: Is this an example of tail recursion? Chris Angelico <rosuav@gmail.com> - 2015-08-06 01:54 +1000
      Re: Is this an example of tail recursion? Rustom Mody <rustompmody@gmail.com> - 2015-08-05 09:10 -0700
        Re: Is this an example of tail recursion? jennyfurtado2@gmail.com - 2015-08-05 09:15 -0700
        Re: Is this an example of tail recursion? Chris Angelico <rosuav@gmail.com> - 2015-08-06 02:28 +1000
          Re: Is this an example of tail recursion? jennyfurtado2@gmail.com - 2015-08-05 09:41 -0700
            Re: Is this an example of tail recursion? Rustom Mody <rustompmody@gmail.com> - 2015-08-05 09:51 -0700
              Re: Is this an example of tail recursion? Chris Angelico <rosuav@gmail.com> - 2015-08-06 03:10 +1000
  Re: Is this an example of tail recursion? Chris Angelico <rosuav@gmail.com> - 2015-08-06 01:51 +1000
    Re: Is this an example of tail recursion? jenny <jennyfurtado2@gmail.com> - 2015-08-05 08:59 -0700

csiph-web