Generere potensen av et tall

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^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\cdot 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}\cdot x^{n/2}$‍. If you were to compute $y=x^{n/2}$‍ recursively, then you could compute $x^n$‍ as $y\cdot y$‍. What if $n$‍ is positive and odd? Then $x^n=x^{n-1}\cdot 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}\cdot x$‍.

What about when $n$‍ is negative? Then $x^n=1/x^{-n}$‍, and the exponent $-n$‍ is positive, since it's the negation of a negative number. 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$‍:

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.