Up: Recursion. Prev: Faster exponentiation.

Comparing our exponentiation algorithms

Here's my solution using our new observation.

function exponentiate(n) {
    if(n == 0) { // base case
        return 1;
    } else if(n % 2 == 0) { // then n is even
        return exponentiate(x * x, n / 2);
    } else { // then n is odd
        return x * exponentiate(x * x, (n - 1) / 2);
    }
}

At the end of the last page, we asked how deep the recursion will go. Here's a way to bound it: Let's look at the call tree for exponentiate(2, 12).

Notice that each time we go one level deeper in the recursion, the value of n at the new level is at most half of what it was. You can see that this will always be true by looking at our definition of exponentiate. (When n is even, the value at the next level is exactly half; when n is odd, the value is a little less.)

If we go log₂ n levels deep, the exponent at that level is at most n * (1/2)^{log₂ n} = 1. When we go one more level deep, the exponent will become 0 and we will have reached the base case. So the deepest the recursion will ever go is 1 + log₂ n levels.

This is much better than the n levels we saw with our first algorithm. This new function is a lot faster.