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

  2. var isEven = function(n) {
  3.     return n % 2 === 0;
  4. };
  6. var isOdd = function(n) {
  7.     return !isEven(n);
  8. };
  10. var power = function(x, n) {
  11.     println("Computing " + x + " raised to power " + n + ".");
  12.     // base case
  13.     if(n === 0) {
  14.         return 1;
  15.     }
  16.     // recursive case: n is negative 
  17.     if(n < 0) {
  18.         return 1 / power(x, -n);
  19.     }
  21.     // recursive case: n is odd
  22.     if(isOdd(n)) {
  23.         return x * power(x, n - 1);
  24.     }
  25.     // recursive case: n is even
  26.     if(isEven(n)) {
  27.         var y = power(x, n/2);
  28.         return y * y;
  29.     }
  30. };
  32. var displayPower = function(x, n) {
  33.     println(x + " to the " + n + " is " + power(x, n));
  34. };
  36. displayPower(3, 0);
  37. Program.assertEqual(power(3, 0), 1);
  38. displayPower(3, 1);
  39. Program.assertEqual(power(3, 1), 3);
  40. displayPower(3, 2);
  41. Program.assertEqual(power(3, 2), 9);
  42. displayPower(3, -1);
  43. Program.assertEqual(power(3, -1), 1/3);
  44. Program.assertEqual(power(4, -1), 1/4);
  45. Program.assertEqual(power(5, -5), Math.pow(5, -5));