Computing powers of a number

Although most languages have a builtin pow function that computes powers of a number, you can write a similar function recursively, and it can be very efficient. The only hitch is that the exponent has to be an integer.

Suppose you want to compute $x^n$, where $x$ is any real number and $n$ is any integer. It's easy if $n$ is $0$, since $x^0 = 1$ no matter what $x$ is. That's a good base case.

So now let's see what happens when $n$ is positive. Let's start by recalling that when you multiply powers of $x$, you add the exponents: $x^a . \space x^b = x^{a + b}$ for any base $x$ and any exponents $a$ and $b$. Therefore, if $n$ is positive and even, then $x^n = x^{n/2} . \space x^{n/2}$. If you were to compute $y = x^{n/2}$recursively, then you could compute $x^n = y . \space y$. What if $n$ is positive and odd? Then $x^n = x^{n-1} . \space x$, and $n - 1$ either is $0$ or is positive and even. We just saw how to compute powers of $x$ when the exponent either is $0$ or is positive and even. Therefore, you could compute $x^{n-1}$ recursively, and then use this result to compute $x^n = x^{n-1} . \space x$. What about when $n$ is negative? Then $x^n = \frac 1 {x^{-n}}$, and the exponent $-n$ is positive. So you can compute $x^{-n}$ recursively and take its reciprocal. Putting these observations together, we get the following recursive algorithm for computing $x^n$​:

• The base case is when $n = 0$, and $x^0 = 1$.

• If $n$ is positive and even, recursively compute $y = x^{n/2}$ and then $x^n = y . \space y$. Notice that you can get away with making just one recursive call in this case, computing $x^{n/2}$ just once, and then you multiply the result of this recursive call by itself.

• If $n$ is positive and odd, recursively compute $x^{n-1}$, so that the exponent either is $0$ or is positive and even. Then, $x^n = x^{n-1} . \space x$

• If $n$ is negative, recursively compute $x^{- n}$, so that the exponent becomes positive. Then, $x^n = \frac 1 {x^{-n}}$.