paulmassimo paulmassimo - 1 month ago 9
Python Question

Exponentiation Recursive

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

n
is even because a doesn't multiply in the
return
.

When I try
recPower(3,2)
, and print the factor step by step, it will be like:

1
3
9

But, why does 3 come out?

def recPower(a, n):
# raises a to the int power n
if n == 0:
return 1
else:
factor = recPower(a, n//2)
if n%2 == 0: # n is even
return factor * factor
else: # n is odd
return factor * factor * a

Answer

Just follow it step by step:

recPower(3, 2)

n != 0 so go down the else branch:

factor = recPower(3, 2//2)

Which is:

recPower(3, 1)

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

or

1 * 1 * 3
Comments