Is this an example of tail recursion?
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 = 9 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) 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: Is this an example of tail recursion?
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 = 9 > > > >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 = 9 > > > >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 > >
Re: Is this an example of tail recursion?
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 = 9 > > > > > > > >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 = 9 > > > > > > > >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 >
How to trace the recursive path?
Consider this code (shown in my previous post)
class CastleDefenseI:
INFINITY = 9
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)
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
solution = CastleDefenseI()
gameSoldiers = 10
castleHits = 11
defendersPerWave = 15
#prints 4
print solution.playGame(gameSoldiers, castleHits, defendersPerWave)
How would I print the path that leads to
if soldiers <= 0 (in oneWave and soldiersVsDefenders)
if defenders<=0 (in soldiersVsDefenders)
I have started going down this direction (incorrect)
class CastleDefenseI:
INFINITY = 9
def __init__(self):
self.dpw = 0
def soldiersVsDefenders(self,soldiers,defenders,path):
# 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
path.append({"soldiers":soldiersLeft,"defenders":defendersLeft,
"castleHits":0})
return 1 + self.soldiersVsDefenders(soldiersLeft,defendersLeft,path)
def oneWave(self,soldiers,defenders,castleHits,path):
# castle/defenders wins
if soldiers <= 0:
print path
return self.INFINITY
# castle is dead, let soldiers play against defenders
if castleHits <= 0:
defendersLeft = defenders - self.dpw
path.append({"soldiers":soldiers,"defenders":defendersLeft,"castleHits":0})
return self.soldiersVsDefenders(soldiers,defendersLeft,path)
# 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)
path = []
path.append({"soldiers":soldiersLeft,"defenders":defendersLeft,"castleHits":castleHitsLeft})
mini = min(mini,1 +
self.oneWave(soldiersLeft,defendersLeft,castleHitsLeft,path))
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
solution = CastleDefenseI()
gameSoldiers = 10
castleHits = 11
defendersPerWave = 15
#prints 4
print solution.playGame(gameSoldiers, castleHits, defendersPerWave)
--
https://mail.python.org/mailman/listinfo/python-list
Re: Is this an example of tail recursion?
On Wednesday, August 5, 2015 at 10:29:21 AM UTC-6, Chris Angelico wrote: > On Thu, Aug 6, 2015 at 2:10 AM, Rustom Mody wrote: > > 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 > > Except that it *isn't* that, precisely because of those other cases. > When Python sees an expression like "1 + x" and doesn't yet know what > x is, it can't do anything other than record the fact that there'll be > a BINARY_ADD of the integer 1 and whatever that thing is. That object > might well define __radd__, so the call is most definitely not > equivalent to the operator. > > And the ultimate result of that addition might not even be a function > call at all, if it's implemented in C. Or if you're running in PyPy > and the optimizer turned it into machine code. So no, even though you > can define addition for *your own classes* using __add__ or __radd__, > you can't reinterpret every addition as a function call. > > ChrisA Good (intricate) point. -- https://mail.python.org/mailman/listinfo/python-list
