LeetCode 50. Pow(x,n)

实现 Pow(x,n) ，即计算 x 的 n 次幂函数（即，\(x^n\)）。

一看到题目，很简单，一个循环能够搞定的问题，但是这是一道中等难度的题目，不可能一个循环就搞定。

刚开始，我按照了循环的思路去解这道题，出现的问题还是挺多的。第一，我默认n为正整数，实际上不是，n还可能为负整数。因此，我们要分开求解。解决这个问题之后，还有一个我需要注意的就是，用循环求解太久了。怎么办？实际上，用递归，每一轮的x都为上一轮x的平方，这样，求解速度就大大增加。

具体操作

n为偶数时，且为正整数时，假设x=2,n=8

更新\(x=x*x,n=n/2;\)

实际上已经求解完了

这就是一个典型的递归问题。

当n为奇数时，实际上，我们只要在原来的基础上再乘以x，就是结果。

如果为n为负整数，其实做法和刚才类似，比如

只需要最好用1/2^8即可解决问题。

现在我们就是开始构造递归

递归其实我们只要确保形式正确，以及要确定一个结束条件

在这一道题目中，我们每次都更新x和n

n=n/2;
return Pow(x*x,n);

我们观察到，n会一直减少，比如\(8\rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 0\)。实际上，我们n变到1就已经符合我们的目的，因为x的n次方，就是x本身。

下面就是实现的代码

class Solution {
public:
    double myPow(double x, int n) {
        //递归实现
        //判断奇偶
        if (n==0){
            return 1;
        }
        if(n==1){
            return x;
        }
        else if(n==-1){
            return 1/x;
        }
        else if(n%2==0){
            //偶数
            n = n/2;
            return myPow(x*x,n);
        }
        else if(n%2!=0&&n>0){
            n = n/2;
            return x*myPow(x*x,n);
        }
        else{
            n = n/2;
            return myPow(x*x,n)/x;
        }
    }
};