# Computing powers of a number

Although JavaScript has 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, start superscript, n, end superscript, where x is any real number and n is any integer. It's easy if n is 0, since x, start superscript, 0, end superscript, equals, 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, start superscript, a, end superscript, dot, x, start superscript, b, end superscript, equals, x, start superscript, a, plus, b, end superscript for any base x and any exponents a and b. Therefore, if n is positive and even, then x, start superscript, n, end superscript, equals, x, start superscript, n, slash, 2, end superscript, dot, x, start superscript, n, slash, 2, end superscript. If you were to compute y, equals, x, start superscript, n, slash, 2, end superscript recursively, then you could compute x, start superscript, n, end superscript as y, dot, y. What if n is positive and odd? Then x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x, and n, minus, 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, start superscript, n, minus, 1, end superscript recursively, and then use this result to compute x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.
What about when n is negative? Then x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript, and the exponent minus, n is positive. So you can compute x, start superscript, minus, n, end superscript recursively and take its reciprocal.
Putting these observations together, we get the following recursive algorithm for computing x, start superscript, n, end superscript:
• The base case is when n, equals, 0, and x, start superscript, 0, end superscript, equals, 1.
• If n is positive and even, recursively compute y, equals, x, start superscript, n, slash, 2, end superscript, and then x, start superscript, n, end superscript, equals, y, dot, y. Notice that you can get away with making just one recursive call in this case, computing x, start superscript, n, slash, 2, end superscript just once, and then you multiply the result of this recursive call by itself.
• If n is positive and odd, recursively compute x, start superscript, n, minus, 1, end superscript, so that the exponent either is 0 or is positive and even. Then, x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.
• If n is negative, recursively compute x, start superscript, minus, n, end superscript, so that the exponent becomes positive. Then, x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.