On Wednesday, August 5, 2015 at 9:21:33 AM UTC-6, Rustom Mody wrote: > 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
On Wednesday, August 5, 2015 at 9:21:33 AM UTC-6, Rustom Mody wrote: > 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 Sorry I am missing a subtle point: Isnt 1+ self.soldiersVsDefenders... ending up calling 1.__add__(self.soldiersVsDefenders...)? -- https://mail.python.org/mailman/listinfo/python-list
