Powers

Pseudo-code

1. The base case $n = 0$, and $x^0 = 1$
2. If $n$ is positive compute recursively $y=x^{(n/2)}$
3. If $n$ is positive and odd, recursively compute $x^{(n - 1)}$
4. If $n$ is negative, compute $x^{-n}$ until n is positive. Then $x^n = 1/x^{-n}$

Implementation

var isEven = function(n) {
    return n % 2 === 0;
};

var isOdd = function(n) {
    return !isEven(n);
};

var power = function(x, n) {
    println("Computing " + x + " raised to power " + n + ".");
    // base case
    if(n === 0) {
        return 1;
    }
    // recursive case: n is negative 
    if(n < 0) {
        return 1 / power(x, -n);
    }

    // recursive case: n is odd
    if(isOdd(n)) {
        return x * power(x, n - 1);
    }
    // recursive case: n is even
    if(isEven(n)) {
        var y = power(x, n/2);
        return y * y;
    }
};

var displayPower = function(x, n) {
    println(x + " to the " + n + " is " + power(x, n));
};

displayPower(3, 0);
Program.assertEqual(power(3, 0), 1);
displayPower(3, 1);
Program.assertEqual(power(3, 1), 3);
displayPower(3, 2);
Program.assertEqual(power(3, 2), 9);
displayPower(3, -1);
Program.assertEqual(power(3, -1), 1/3);
Program.assertEqual(power(4, -1), 1/4);
Program.assertEqual(power(5, -5), Math.pow(5, -5));