50. Pow(x, n) (Medium)

Implement pow(x, n).

Solution 1: recursive

double myPow(double x, int n) {
    if (n < 0) return 1 / power(x, -n);
    return power(x, n);
}
double power(double x, int n) {
    if (n == 0) return 1;
    double half = power(x, n / 2);
    return (n % 2 == 0) ? half * half: x * half * half;
}

Solution 2:

还有一种写法可以只用一个函数即可，在每次递归中就检查n的正负，然后做相应的变换即可，代码如下：

double myPow(double x, int n) {
    if (n == 0) return 1;
    double half = myPow(x, n/2);
    if (n % 2 == 0) return half*half;
    else if (n > 0) return x*half*half;
    else return half*half/x;
}

Solution 3: iterative

这道题还有迭代的解法，我们让i初始化为n，然后看i是否是2的倍数，是的话x乘以自己，否则res乘以x，i每次循环缩小一半，直到为0停止循环。最后看n的正负，如果为负，返回其倒数，参见代码如下：

double myPow(double x, int n) {
    double res = 1.0;
    for (int i = n; i != 0; i /= 2) {
        if (i % 2) res *= x;
        x *= x;
    }
    return (n < 0) ? 1/res:res;
}