Is this an example of tail recursion?

[Rustom Mody]

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)