Is this an example of tail recursion?
jennyfurtado2 at gmail.com
jennyfurtado2 at gmail.com
Wed Aug 5 12:15:22 EDT 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