On Wednesday, August 5, 2015 at 9:52:14 AM UTC-6, Chris Angelico wrote: > On Thu, Aug 6, 2015 at 1:13 AM, <jennyfurta...@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. -- https://mail.python.org/mailman/listinfo/python-list
