Up: Recursion. Prev: Exponentiation. Next: Comparison.

Faster exponentiation

Here is my implementation of the exponentiate function: 

function exponentiate(x, n) {
    if(n == 0) {
        return 1;
    } else {
        return x * exponentiate(x, n - 1);
    }
}

Unfortunately, this is slow when n is large, since it requires going down n levels of recursion. If n is 1000, the computer will have to go through 1000 levels of recursion. This takes a while, and it extends the resources of computers, which are often not designed to handle call stacks that big. (It crashed my browser.)

Fortunately, recursion suggests a faster way by noticing a different fact about exponents:

If n is even, then xn = (x2)n/2
If n is odd, then xn = x * (x2)(n-1)/2

Use this fact to write a new implementation of exponentiate.

function exponentiate(x, n) {
    
}
x:
n:
Answer:

Here's a question: How many levels will the recursion go for general n?

Next: Comparison.