paulmassimo - 1 year ago 114
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
``````

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download