On Thu, Aug 6, 2015 at 1:13 AM, <jennyfurta...@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
--
https://mail.python.org/mailman/listinfo/python-list
