a to the power of b

Recursion (if b == 1000, result = a^500 * a^500) base case： b == 0 return 1; 正负不用再考虑， 因为不能被二整除会单独乘以一个a。

public class Solution {
  public long power(int a, int b) {
    // Write your solution here
    if (a == 0) {
      return 0;
    }
    if (b == 0) {
      return 1;
    }
    long half = power(a, b / 2);
    if ( b % 2 == 1) {
      return half * half * a;
    } else {
      return half * half;
    }
  }
}