Is this an example of tail recursion?

[jenny]

On Wednesday, August 5, 2015 at 9:52:14 AM UTC-6, Chris Angelico wrote:
> On Thu, Aug 6, 2015 at 1:13 AM,  <jennyfurtado2 at 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

Thank you Chris! That was a very nice explanation.