Is this an example of tail recursion?
jennyfurtado2 at gmail.com
jennyfurtado2 at gmail.com
Wed Aug 5 11:37:37 EDT 2015
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... at 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... at 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...)?
More information about the Python-list
mailing list