On Wednesday, August 5, 2015 at 9:07:52 PM UTC+5:30, jennyf...@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...@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...@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) -- https://mail.python.org/mailman/listinfo/python-list
