Is this an example of tail recursion?
jennyfurtado2 at gmail.com
jennyfurtado2 at gmail.com
Wed Aug 5 11:13:11 EDT 2015
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)
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