Is this an example of tail recursion?
Rustom Mody
rustompmody at gmail.com
Wed Aug 5 18:10:09 CEST 2015
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)
More information about the Python-list
mailing list