Leetcode 50: POW(x, n)

Implement pow(x, n).

本题要求实现x ^ n， 由于pow(x, n) = pow(x, n-1) * x; 这样递归的话递归层次太多，容易超时，可以通过二分法递归，每次递归n/2, pow(x, n) = pow(x,n/2) * pow(x, n/2); (n is even number)

数学计算中： 二分法递归是很常见的递归优化法，可以节省很多时间， half * half 

本题中还要注意的一点是，n 可能取值是 : n > 0; n == 0; n < 0 .可以先取n的绝对值， 获得n为正数的解，再对n进行处理。

由于对n进行了二分，整个算法的时间复杂度是O（logn）

class Solution {
private:
    double helper(double x, int n) {
        //base case
        if (x == 0) return 0;
        if (x == 1) return 1;
        if (n == 0) return 1;
        double half = myPow(x, n/2);
        if (n % 2) return half * half * x;
        return half * half;
    }
public:
 //use recursion
    double myPow(double x, int n) {
        double rst = helper(x, abs(n));
        if (n < 0) {
            return 1.0/rst;
        } else {
            return rst;
        }
    }
};