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

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

Use this fact to write a new implementation of
`exponentiate`.

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

Next: Comparison.