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 xn, where x is any real number and n is any integer. It's easy if n is 0, since x0 = 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:  xa⋅xb = xa+b for any base x and any exponents a and b. Therefore, if n is positive and even, then xn = xn/2 ⋅ xn/2. If you were to compute y = xn/2 recursively, then you could compute xn = y ⋅ y. What if n is positive and odd? Then xn = xn-1 ⋅ 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 xn-1 recursively, and then use this result to compute xn = xn-1 ⋅ xWhat about when n is negative? Then xn = 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 xn​ :

  • The base case is when n = 0, and x0 = 1.
  • If n is positive and even, recursively compute y = xn/2, and then xn = y ⋅ y. Notice that you can get away with making just one recursive call in this case, computing xn/2 just once, and then you multiply the result of this recursive call by itself.
  • If n is positive and odd, recursively compute xn-1, so that the exponent either is 0 or is positive and even. Then, xn = xn-1 ⋅ x
  • If n is negative, recursively compute x-n, so that the exponent becomes positive. Then, xn = 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