I am learning this Exponentiation Recursive algorithm, it works well.
But I don't understand why this works?
Because I expect that always returns 1,1,1...if
def recPower(a, n):
# raises a to the int power n
if n == 0:
factor = recPower(a, n//2)
if n%2 == 0: # n is even
return factor * factor
else: # n is odd
return factor * factor * a
Just follow it step by step:
n != 0 so go down the else branch:
factor = recPower(3, 2//2)
In this recursive step
n != 0 we follow the first else branches,
1%2 != 0 so we follow the second else branch. The factor is therefore 1 and
a == 3.
The return value of this step is therefore:
factor * factor * a
1 * 1 * 3