Up: Recursion. Prev: Faster exponentiation.

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).

If we go log_{2} `n` levels deep, the exponent at
that level is at most
`n` * (1/2)^{log2 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_{2} `n` levels.

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