Help with creating Recursive Algorithms

Question

Prove your algorithms correct.

• Write an (efficient) recursive algorithm Pow (a,n) than computes $ (a \in \mathbb R)(n \in \mathbb Z):n\geq 0, a^n $.

• Write a recursive algorithm that computes $a^{2^n}$.

This is what I have tried so far on the first one (not sure if its right):

pow(a, n)

{

    if n == 0

        return 1

    else

        return a*pow(a, n-1)

}

Answer 1

Have you tested your algorithm? It fails for pow$(2,2)$, returning $1$ instead of $4$. Arpan showed the fix. Then you have the problem of "efficient" Your algorithm is $O(n)$ If you do Exponentiation by squaring you can do better. For the second, the naive thing is to use your pow function from the first. As it didn't call for efficient separately, you could argue that is acceptable, but you can do better.

Answer 2

To make it more efficient, after the "n == 0" case, insert this:

if n is even, return $(pow(a, n/2))^2$

This is correct because $a^{2m} = (a^m)^2$.

This also makes the running time of order $\log n$, instead of order $n$, which is a good thing.

As is often the case, nothing here is original.