paulmassimo - 9 months ago 82

Python Question

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`

`return`

When I try

`recPower(3,2)`

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
```

Source (Stackoverflow)