**recurPower** I got it but I dont understand it

Question

Ok, let me start by saying yes this is homework. But I have the answer (played with it til it worked) my question is more on "how" I have had the teacher explain it multiple times (online class) but I am just not getting it, hoping that someone on here is better at explaining things the way I think about them.

Here is the assignment:

Write a function recurPower(base, exp) which computes base**exp by recursively calling itself to solve a smaller version of the same problem, and then multiplying the result by base to solve the initial problem.

This function should take in two values - base can be a float or an integer; exp will be an integer ≥0. It should return one numerical value. Your code must be recursive - use of the ** operator or looping constructs is not allowed.

Ok, so after a few attempts with trial and error (by this I mean a few hours of changing things wildly) I came up with the correct code and it solved for the correct answers, but I dont understand how.

Here is the code:

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

returns: int or float, base^exp
'''

if exp <= 0:
    return 1


return base * recurPower(base, exp - 1)

First thing is the part where exp = 0 then return is 1.... I dont understand why anything would come back with 1. Second is if the final part of the code, if there is no loop where does the exp drop by 1?

Answer 1

The first issue is why does exp <= 0 return 1.

By definition, anything with a 0 as an exponent is 1. So,

1^0 => 1
2^0 => 1
...

As for the second part, this is recursion at work. If I call recurPower(2, 6) I will get a series of calls that looks like

recurPower(2, 6) =>
2 * recurPower(2, 5) =>
2 * 2 * recurPower(2, 4) =>
...
2 * 2 * 2 * 2 * 2 * 2 * 1

which is the answer.

So, in English, 2 ^ 6 is the exact same as 2 * 2 ^ 5. We use this rule to break it down into simpler and simpler exponents.

Answer 2

pow(2, 3)
= 2 * pow(2, 2)
= 2 * (2 * pow(2, 1))
= 2 * (2 * (2 * (pow 2, 0)))
= 2 * (2 * (2 * 1))) ; base case: n=0 -> return 1
= 2 * (2 * 2)
= 2 * 4
= 8

In every recursion, you need a base case, i.e. a condition where the recursion stops, otherwise it never ends. In a multiplication, the base case is likely to return 1 because multiplying by 1 is neutral, i.e. it doesn't affect the previous calculations.

Other than the base case, you have the general case where you express something in terms of something "smaller", here: n^x = n * n^(x-1), until you hit the base case when x=0.