Exponentiation Recursive
<p>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 <code>n</code> is even because a doesn't multiply in the <code>return</code>.<br>
When I try <code>recPower(3,2)</code>, and print the factor step by step, it will be like:</p>

<p>1
3
9</p>

<p>But, why does 3 come out?</p>

<pre><code> 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
</code></pre>

<p>Just follow it step by step:</p>

<pre><code>recPower(3, 2)
</code></pre>

<p><code>n != 0</code> so go down the else branch:</p>

<pre><code>factor = recPower(3, 2//2)
</code></pre>

<p>Which is:</p>

<pre><code>recPower(3, 1)
</code></pre>

<p>In this recursive step <code>n != 0</code> we follow the first else branches, <code>1%2 != 0</code> so we follow the second else branch. The factor is therefore 1 and <code>a</code> == 3.</p>

<p>The return value of this step is therefore:</p>

<pre><code>factor * factor * a
</code></pre>

<p>or</p>

<pre><code>1 * 1 * 3
</code></pre>

python python-3.x computer-science