# 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 ** **no matter what

So now let's see what happens when ** **for any base

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}}$ .

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy