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 xnx^n, where xx is any real number and nn is any integer. It's easy if nn is 00, since x0=1x^0 = 1 no matter what xx is. That's a good base case.

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

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

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

  • If nn is positive and odd, recursively compute xn1x^{n-1}, so that the exponent either is 00 or is positive and even. Then, xn=xn1. xx^n = x^{n-1} . \space x

  • If nn is negative, recursively compute xnx^{- n}, so that the exponent becomes positive. Then, xn=1xnx^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