Is this an example of tail recursion?

Rustom Mody rustompmody at gmail.com
Wed Aug 5 17:21:21 CEST 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