Is this an example of tail recursion?

[jennyfurtado2 at gmail.com]

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...)?