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...@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)
Thanks Rustom. I get the __add__ point now. -- https://mail.python.org/mailman/listinfo/python-list
