On Wednesday, August 5, 2015 at 8:43:31 PM UTC+5:30, jennyf...@gmail.com wrote: > I am trying to learn differences between tail recursion and non tail > recursion. > > 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? > > class CastleDefenseI: > INFINITY = 999999999 > > def __init__(self): > self.dpw = 0 > > def soldiersVsDefenders(self,soldiers,defenders): > # soldiers win > if defenders <=0: > return 0 > # castle/defenders win > if soldiers <= 0: > return self.INFINITY > > # do another round of fighting > # 1. Soldiers kill as many defenders > defendersLeft = defenders - soldiers > # 2. defendersLeft kill as many soldiers > soldiersLeft = soldiers - defendersLeft > return 1 + self.soldiersVsDefenders(soldiersLeft,defendersLeft)
Yes it *looks* tail recursive However if you rewrite 1 + x as 1 .__add__(x) you get return 1 .__add__(self.soldiersVsDefenders(soldiersLeft,defendersLeft)) Now you can see its not tail recursive I guess the same applies to the other functions > > def oneWave(self,soldiers,defenders,castleHits): > # castle/defenders wins > if soldiers <= 0: > return self.INFINITY > # castle is dead, let soldiers play against defenders > if castleHits <= 0: > defendersLeft = defenders - self.dpw > return self.soldiersVsDefenders(soldiers,defendersLeft) > > # try every possibility: > # 1) all soldiers hit the castle, none hits the defenders > # 2) one soldier hits the castle, the others hit the defenders > # 3) two soldiers hit the castle, the others hit the defenders > # ... > # soldiers) no soldier hits the castle, all others hit the > # defenders > 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 > > def playGame(self,soldiers,castleHits,defendersPerWave): > self.dpw = defendersPerWave > numWaves = self.oneWave(soldiers,0,castleHits) > if numWaves >= self.INFINITY: > return -1 > else: > return numWaves -- https://mail.python.org/mailman/listinfo/python-list
