Is this an example of tail recursion?

jennyfurtado2 at gmail.com jennyfurtado2 at gmail.com
Wed Aug 5 17:13:11 CEST 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