J.B94 J.B94 - 7 months ago 11
Python Question

how does this recursive statement work?

I have two recursive statements that do the same thing, i understand how the first one works but I am confused on the second case.

1)

def recurPower(base, exp):
'''
base: int or float.
exp: int >= 0

returns: int or float, base^exp
'''
# Base case is when exp = 0
if exp <= 0:
return 1

# Otherwise, exp must be > 0, so return
# base* base^(exp-1). This is the recursive case.
return base * recurPower(base, exp - 1)


this first case although it is recalling itself it still leaves a variable "base" behind to multiply every time around the method.

2)

def recurPowerNew(base, exp):
'''
base: int or float.
exp: int >= 0

returns: int or float; base^exp
'''
# Base case is when exp = 0
if exp <= 0:
return 1

# Recursive case 1: exp > 0 and even
elif exp % 2 == 0:
return recurPowerNew(base*base, exp/2)

# Otherwise, exp must be > 0 and odd, so use the second
# recursive case.
return base * recurPowerNew(base, exp - 1)


In this case I don't understand how it works if it is an even number, there is no variable like in the first case that is being acted upon, when the number is even it seems to just constantly give itself different parameters but at no point does it actually address any particular variable such as "base".

do parameters return a value if there is no body in the method?

Answer

Let's take an example:

print recurPowerNew(3, 4)

so base is 3 and exp is 8. This will fall into the case you are concerned with, and call:

return recurPower(9, 2)

... which will also fall into the same case, and call

return recurPower(81, 1)

ah-ha! This is the odd case. So this will call:

return 81 * recurPower(81, 0)

The second term of the multiplication is 1, so we return 81 all the way up the stack. If you follow this through, it also works for numbers that are not powers of two.

The point of this, is that it is much more efficient than the first method. It will produce one or two stack frames per bit of the exponent. The first method will produce exponent stack frames!