Up: Recursion. Prev: Closed-form solution. Next: Faster exponentiation.

Exponentiation

Now let's consider a more practical example: exponentiating a number.

This time, let's use JavaScript rather than pseudocode. A recursive function in JavaScript is written just as you would expect: Call the function just as you would any other function. For example, the following function computes a Fibonacci number:

function fib(n) {
    if(n <= 1) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

Complete the following function, which takes two numbers, x and n and should return xⁿ. You should assume that n is a non-negative integer. (If you need a hint, look here.)

function exponentiate(x, n) {
    
}

After you finish writing this function, you can continue, where we'll see a correct implementation for you to compare with, and then we'll look at how recursion suggests a faster way to exponentiate two numbers.

Next: Faster exponentiation.