Is this an example of tail recursion?

jennyfurtado2 at gmail.com jennyfurtado2 at gmail.com
Wed Aug 5 18:15:22 CEST 2015


On Wednesday, August 5, 2015 at 10:10:22 AM UTC-6, Rustom Mody wrote:
> On Wednesday, August 5, 2015 at 9:07:52 PM UTC+5:30, jennyf... at gmail.com wrote:
> > 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...)?
> 
> 1 + x
> does not *call* 1 .__add__(x)
> It *is* that
> [Barring corner cases of radd etc]
> IOW I am desugaring the syntax into explicit method-calls so you can see
> all the calls explicitly
> Then it becomes evident -- visibly and in fact --that the tail call is the 
> __add__ method not the solderdiersVsDefenders
> 
> As for Chris':
> > I think his point is that it is, in effect, doing that; but honestly,
> > calling this a tail call into the int+int addition function is pretty
> > pointless. I mean, sure, it's technically a sort of tail call, but
> > it's definitely not tail recursion, and it's such a trivial operation
> > (adding one to a probably-small number) that it's hardly even worth
> > mentioning. The main point of tail recursion is how it interacts with
> > the self-call, and that's not the tail call here. 
> 
> Ive no idea what he is saying.
> Tail-call has nothing to do with triviality or otherwise of computation
> 
> When you do
> return foo(bar(baz(x)))
> foo is a tail call; bar and baz not.
> 
> Tail recursion is a special case of tail call where that expression is
> embedded in a definition of foo
> 
> Languages like scheme take pains to eliminate ALL tail calls
> Not python so your question is a bit academic (in python context)

Thanks Rustom. I get the __add__ point now.


More information about the Python-list mailing list