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