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