My blog

pow.java

/* Fully recursive */
public int pow(int b, int e) {
  if(b == 0) return 1;
  if(e%2 == 0) return pow(b*b, e/2);
  return b*pow(b, e-1);
}

/* tail recursive */
public int pow(int b, int e) { return _pow(b,e,1); }
public int _pow(int b, int e, int ans) {
  if(b==0) return ans;
  if(e%2==0) return _pow(b*b, e/2, ans);
  return _pow(b, e-1, ans*b);
}

/* unroll tail recursion */
public int pow(int b, int e) {
  int ans = 1;
  while(e > 0) {
    if(e%2==1) {
      ans *= b;
      e--;
    }
    else {
      b*=b;
      e/=2;
    }
  }
  return ans;
}

/* After the odd case, we'll always be even next time.
 * We also see that "e--" was unnecessary.
 * This is now the "canonical" imperative solution.
 */
public int pow(int b, int e) {
  int ans = 1;
  while(e > 0) {
    if(e%2==1) {
      ans *= b;
    }
    b*=b;
    e/=2;
  }
  return ans;
}