Re: Is this an example of tail recursion?
On Thu, Aug 6, 2015 at 2:51 AM, Rustom Mody wrote:
> And I continue to have no idea what Chris is talking about.
> Here is C printf
from ctypes import *
cdll.LoadLibrary("libc.so.6")
libc = CDLL("libc.so.6")
libc.printf(b"%s", b"Hello")
> 5
> Hello>>>
>
> As far as I can see printf is a C function and its behaving like (an
> ill-behaved) python function as well.
> Likewise for anything else written ina C extension module
> Or a C-builtin
>
> If its callable from within python its python
> That it may also be C seems to me beside the point
> [As I said I dont get the point]
Sure, if it's callable from within Python. Where is this implemented in CPython?
def f(x): return x+2
f(1)
There's PyNumber_Add() in abstract.c, which looks for the nb_add slot.
That contains a pointer to long_add, which is defined in longobject.c.
Is that the same thing as (1).__add__? Not really, but that's kinda
what implements the underlying operation. Also, the function is
declared as 'static', so I don't think you can find it using ctypes.
Adding two Python objects is *not* a function call. It is an
operator-controlled action. It's very similar, in many ways, to a
method call, but it isn't exactly that, and it certainly isn't the
sort of thing that you could tail-call-optimize as the concept applies
only to cases where you can actually replace a stack frame.
ChrisA
--
https://mail.python.org/mailman/listinfo/python-list
Re: Is this an example of tail recursion?
On Wednesday, August 5, 2015 at 10:11:30 PM UTC+5:30, wrote:
> 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.
And I continue to have no idea what Chris is talking about.
Here is C printf
>>> from ctypes import *
>>> cdll.LoadLibrary("libc.so.6")
>>> libc = CDLL("libc.so.6")
>>> libc.printf(b"%s", b"Hello")
5
Hello>>>
As far as I can see printf is a C function and its behaving like (an
ill-behaved) python function as well.
Likewise for anything else written ina C extension module
Or a C-builtin
If its callable from within python its python
That it may also be C seems to me beside the point
[As I said I dont get the point]
--
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
Re: Is this an example of tail recursion?
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 -- https://mail.python.org/mailman/listinfo/python-list
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 >
Re: Is this an example of tail recursion?
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 > > ># 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
Re: Is this an example of tail recursion?
On Wednesday, August 5, 2015 at 9:52:14 AM UTC-6, Chris Angelico wrote: > On Thu, Aug 6, 2015 at 1:13 AM, wrote: > > I am trying to learn differences between tail recursion and non tail > > recursion. > > Tail recursion is where you do exactly this: > > return some_function(...) > > Absolutely nothing is allowed to happen around or after that function, > and that also means you can't do that inside a try/except/finally > block, nor a with block, etc, etc, etc. It has to be nothing more than > a function call, and you return the exact result of that call. > > > 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? > > > >def __init__(self): > >self.dpw = 0 > > Not tail recursive - not recursive - doesn't call anything. Trivial case. :) > > >def soldiersVsDefenders(self,soldiers,defenders): > ># soldiers win > >if defenders <=0: > > return 0 > ># castle/defenders win > >if soldiers <= 0: > > return self.INFINITY > > In these cases, equally trivial - not recursive in any form. > > ># do another round of fighting > ># 1. Soldiers kill as many defenders > >defendersLeft = defenders - soldiers > ># 2. defendersLeft kill as many soldiers > >soldiersLeft = soldiers - defendersLeft > > (Interesting that the attacking soldiers get the first strike.) > > >return 1 + self.soldiersVsDefenders(soldiersLeft,defendersLeft) > > This is NOT tail recursion, because you add 1 at the end of it. The > way to make it tail recursive would be to add another argument to the > function, which it would keep adding to; whenever it returns, you > would add the accumulator to the return value: > > def soldiersVsDefenders(self,soldiers,defenders, accum=0): > if defenders <= 0: > return 0 + accum > if soldiers <= 0: > return self.INFINITY + accum > # other code goes here > return self.soldiersVsDefenders(soldiersLeft,defendersLeft,1+accum) > > Now it's tail recursive. If this looks ugly, it's because it is; tail > recursion often isn't worth the effort. > > Note that, as far as Python's concerned, this is a tail call, but > isn't necessarily *recursion* (which implies that you somehow know > you're calling the same function). If someone subclasses your code and > overrides this method, your code will call the subclass's version - if > the subclass calls through to super(), you'll end up with mutual > recursion, but still not a simple case of tail recursion. However, you > could choose to ignore this possibility and manually convert this into > iteration: > > def soldiersVsDefenders(self,soldiers,defenders): > rounds = 0 > while soldiers and defenders: > # do another round of fighting > # 1. Soldiers kill as many defenders > defendersLeft = defenders - soldiers > # 2. defendersLeft kill as many soldiers > soldiersLeft = soldiers - defendersLeft > rounds += 1 > if defenders <= 0: > return rounds > return self.INFINITY + rounds > > How's that look? Better? Worse? > > On to the next function. > > >def oneWave(self,soldiers,defenders,castleHits): > ># castle is dead, let soldiers play against defenders > >if castleHits <= 0: > >defendersLeft = defenders - self.dpw > >return self.soldiersVsDefenders(soldiers,defendersLeft) > > This is a tail call. It's not tail *recursion* because you're calling > a completely different function, but you are indeed calling another > function and directly returning its return value. > > >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 > > Not sure what the point of all this is, but sure. This clearly isn't > tail recursion, though, as it's doing a whole lot of other work after > the recursive call. Having a loop and recursion like this is pretty > scary, but in terms of "is this or isn't this tail recursive", it's > pretty clear. > > >def playGame(self,soldiers,castleHits,defendersPerWave): > >self.dpw = defendersPerWave > >numWaves = self.oneWave(soldiers,0,castleHits) > >if numWaves >= self.INFINITY: > > return -1 > >else: > > return numWaves > > And this is, again, no tail call. If the trap for INFINITY becoming -1 > were inside oneWave(), then this could be turned into a tail call, but > as it is, there's more work to be done after the other function > returns, so it's not a tail call. > > Hope that h
Re: Is this an example of tail recursion?
On Thu, Aug 6, 2015 at 1:37 AM, wrote: > Sorry I am missing a subtle point: Isnt 1+ self.soldiersVsDefenders... ending > up calling 1.__add__(self.soldiersVsDefenders...)? 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. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: Is this an example of tail recursion?
On Thu, Aug 6, 2015 at 1:13 AM, wrote: > I am trying to learn differences between tail recursion and non tail > recursion. Tail recursion is where you do exactly this: return some_function(...) Absolutely nothing is allowed to happen around or after that function, and that also means you can't do that inside a try/except/finally block, nor a with block, etc, etc, etc. It has to be nothing more than a function call, and you return the exact result of that call. > 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? > >def __init__(self): >self.dpw = 0 Not tail recursive - not recursive - doesn't call anything. Trivial case. :) >def soldiersVsDefenders(self,soldiers,defenders): ># soldiers win >if defenders <=0: > return 0 ># castle/defenders win >if soldiers <= 0: > return self.INFINITY In these cases, equally trivial - not recursive in any form. ># do another round of fighting ># 1. Soldiers kill as many defenders >defendersLeft = defenders - soldiers ># 2. defendersLeft kill as many soldiers >soldiersLeft = soldiers - defendersLeft (Interesting that the attacking soldiers get the first strike.) >return 1 + self.soldiersVsDefenders(soldiersLeft,defendersLeft) This is NOT tail recursion, because you add 1 at the end of it. The way to make it tail recursive would be to add another argument to the function, which it would keep adding to; whenever it returns, you would add the accumulator to the return value: def soldiersVsDefenders(self,soldiers,defenders, accum=0): if defenders <= 0: return 0 + accum if soldiers <= 0: return self.INFINITY + accum # other code goes here return self.soldiersVsDefenders(soldiersLeft,defendersLeft,1+accum) Now it's tail recursive. If this looks ugly, it's because it is; tail recursion often isn't worth the effort. Note that, as far as Python's concerned, this is a tail call, but isn't necessarily *recursion* (which implies that you somehow know you're calling the same function). If someone subclasses your code and overrides this method, your code will call the subclass's version - if the subclass calls through to super(), you'll end up with mutual recursion, but still not a simple case of tail recursion. However, you could choose to ignore this possibility and manually convert this into iteration: def soldiersVsDefenders(self,soldiers,defenders): rounds = 0 while soldiers and defenders: # do another round of fighting # 1. Soldiers kill as many defenders defendersLeft = defenders - soldiers # 2. defendersLeft kill as many soldiers soldiersLeft = soldiers - defendersLeft rounds += 1 if defenders <= 0: return rounds return self.INFINITY + rounds How's that look? Better? Worse? On to the next function. >def oneWave(self,soldiers,defenders,castleHits): ># castle is dead, let soldiers play against defenders >if castleHits <= 0: >defendersLeft = defenders - self.dpw >return self.soldiersVsDefenders(soldiers,defendersLeft) This is a tail call. It's not tail *recursion* because you're calling a completely different function, but you are indeed calling another function and directly returning its return value. >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 Not sure what the point of all this is, but sure. This clearly isn't tail recursion, though, as it's doing a whole lot of other work after the recursive call. Having a loop and recursion like this is pretty scary, but in terms of "is this or isn't this tail recursive", it's pretty clear. >def playGame(self,soldiers,castleHits,defendersPerWave): >self.dpw = defendersPerWave >numWaves = self.oneWave(soldiers,0,castleHits) >if numWaves >= self.INFINITY: > return -1 >else: > return numWaves And this is, again, no tail call. If the trap for INFINITY becoming -1 were inside oneWave(), then this could be turned into a tail call, but as it is, there's more work to be done after the other function returns, so it's not a tail call. Hope that helps! ChrisA -- 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 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 -- https://mail.python.org/mailman/listinfo/python-list
