Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #95021 > unrolled thread

Is this an example of tail recursion?

Back to article view | Back to comp.lang.python

Contents

  Is this an example of tail recursion? jennyfurtado2@gmail.com - 2015-08-05 08:13 -0700
    Re: Is this an example of tail recursion? Rustom Mody <rustompmody@gmail.com> - 2015-08-05 08:21 -0700
      Re: Is this an example of tail recursion? jennyfurtado2@gmail.com - 2015-08-05 08:37 -0700
        Re: Is this an example of tail recursion? Chris Angelico <rosuav@gmail.com> - 2015-08-06 01:54 +1000
        Re: Is this an example of tail recursion? Rustom Mody <rustompmody@gmail.com> - 2015-08-05 09:10 -0700
          Re: Is this an example of tail recursion? jennyfurtado2@gmail.com - 2015-08-05 09:15 -0700
          Re: Is this an example of tail recursion? Chris Angelico <rosuav@gmail.com> - 2015-08-06 02:28 +1000
            Re: Is this an example of tail recursion? jennyfurtado2@gmail.com - 2015-08-05 09:41 -0700
              Re: Is this an example of tail recursion? Rustom Mody <rustompmody@gmail.com> - 2015-08-05 09:51 -0700
                Re: Is this an example of tail recursion? Chris Angelico <rosuav@gmail.com> - 2015-08-06 03:10 +1000
    Re: Is this an example of tail recursion? Chris Angelico <rosuav@gmail.com> - 2015-08-06 01:51 +1000
      Re: Is this an example of tail recursion? jenny <jennyfurtado2@gmail.com> - 2015-08-05 08:59 -0700

#95021 — 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 = 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)

   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

[toc] | [next] | [standalone]

#95022

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

[toc] | [prev] | [next] | [standalone]

#95023

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...)?

[toc] | [prev] | [next] | [standalone]

#95025

On Thu, Aug 6, 2015 at 1:37 AM,  <jennyfurtado2@gmail.com> 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

[toc] | [prev] | [next] | [standalone]

#95027

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)

[toc] | [prev] | [next] | [standalone]

#95028

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.

[toc] | [prev] | [next] | [standalone]

#95029

On Thu, Aug 6, 2015 at 2:10 AM, Rustom Mody <rustompmody@gmail.com> 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

[toc] | [prev] | [next] | [standalone]

#95031

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 <rustompmody@gmail.com> 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. 

[toc] | [prev] | [next] | [standalone]

#95032

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]

[toc] | [prev] | [next] | [standalone]

#95033

On Thu, Aug 6, 2015 at 2:51 AM, Rustom Mody <rustompmody@gmail.com> 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

[toc] | [prev] | [next] | [standalone]

#95024

On Thu, Aug 6, 2015 at 1:13 AM,  <jennyfurtado2@gmail.com> 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

[toc] | [prev] | [next] | [standalone]

#95026

On Wednesday, August 5, 2015 at 9:52:14 AM UTC-6, Chris Angelico wrote:
> On Thu, Aug 6, 2015 at 1:13 AM,  <jennyfurtado2@gmail.com> 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

Thank you Chris! That was a very nice explanation.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web