50. Pow

recursive squaring method. 直接x * pow(x, n - 1)是O(n)的复杂度 ，会发生maximum recursion depth exceeded，如测试用例1.00001 123456，所以对输入n减半处理，并进行奇偶判断。比如16=4*4，只要对4进行相乘即可求出结果。

public double myPow(double x, int n) {
    if (n < 0) return 1/dfs(x, -n);
    return dfs(x, n);
}

public double dfs(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x; // 这个base case有时候可以减少一次递归
    double v = dfs(x, n >>> 1); // n/2
    if ((n & 1) == 0) {  // n % 2 == 0 注意优先级 & < ==
        return v * v;
    } else {
        return v * v * x;
    }
}

一个例子

1.00001 123456
1.00001 61728
1.00001 30864
1.00001 15432
1.00001 7716
1.00001 3858
1.00001 1929
1.00001 964
1.00001 482
1.00001 241
1.00001 120
1.00001 60
1.00001 30
1.00001 15
1.00001 7
1.00001 3
3.4368447520767935

>>出错

1.00000
-2147483648