【递归】Pow(x,n)：一道对递归的认识体现得淋漓尽致的题目！

50. Pow(x, n)

50. Pow(x, n)

​ 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• n 是一个整数
• 要么 x 不为零，要么 n > 0 。
• -104 <= xn <= 104

解题思路：递归 + 二分思想

​ 这道题有两个解法，其中解法一就是直接递归（迭代也是可以的） n 次然后进行累乘，这个思路并不难想到，因为每一步的操作其实都是一致的，但是对于这道题来说，这种解法是会超时的，时间复杂度为 O(n)，因为这道题有更优的解法！

​ 解法二就是结合递归与二分的思想，我们仔细一想，其实我们可以没必要真的操作 n 次进行累乘，而是可以对指数进行不断的二分求解每一部分的结果，最后再对所有二分后的结果进行合并，相当于归并的思想！

​ 也就是说快速幂的核心：对指数进行二分的形式处理！如下图所示：

​ 当我们处理 3^16 的时候，就可以拆分为两个 3^8 进行相乘，然后我们再递归求一下 3^4 是多少，以此类推，直到最后指数为 0 的情况就停止，然后进行返回，返回的就是两个当前求出来的拆分后的数的乘积，比如处理 3^16 的时候，拆分为两个 3^8，此时递归函数完成之后返回的就是 3^8 的大小，那么我们只需要拿 3^8 与 3^8 累乘就得到了 3^16，以此类推！

​ 这样的处理方式，也就是二分思想，时间复杂度为 O(logn)，而当 n 越大的时候，这种快速幂的求法的效果就越明显！

​

​ 所以我们分为三步来总结一下快速幂的求法：

函数头的设计：

因为我们希望递归函数能返回一个最后的结果，所以返回值就是 double，然后因为需要用到题目给的底数 x 以及当前的 n 的大小，所以也要有一个 double 类型的底数 x，以及一个 long long 类型的指数 count，如下所示：

double dfs(double x, long long count);

至于这里的指数为什么要传一个 long long 类型，其实是这道题的一个细节，因为我们 对于指数为负数的情况进行处理的时候，其实就相当于是对其绝对值的也就是正数的操作，最后让 1 除以这个结果即可，而又因为 int 类型的范围是 -2^31 ~ 2^31-1，如果此时我们对于负数 -2^31 取绝对值的话，此时变成正数之后就超出了正数的范围了，也就是溢出了，所以会报错，所以在传参的时候可以 使用 long long 类型来防止溢出的情况！

函数体的内容：

首先采用的是后序遍历的思想，也就是先拿到后面的结果，再对该结果进行处理，相当于对下一层的二分进行了归并！

但是还有一个细节上面没有提到，就是有可能指数是除不尽的，如果指数是奇数的话，比如说 3^5，将其分解为两个 3^2 之后，如果不多做处理的话，此时就会漏了一个 3^1，所以我们需要 判断一下指数是奇数还是偶数，如果是奇数的话则需要在每次得到结果进行累乘的时候多乘一次 x，防止漏掉情况！

// 快速幂的核心：对指数进行二分的形式处理
// 进行后序遍历，拿到后面的结果，再对该结果进行处理，相当于对上面的二分又进行了归并！
// 比如2^16，二分之后就是两个2^8，拿到2^8之后只需要让两者相乘就拿到了2^16
// 但是要注意如果指数二分之后有余数的话，那么还需要再乘一次x，才不会遗漏
double ret = dfs(x, count / 2);
if(count % 2 == 0)
    return ret * ret;
else 
    return ret * ret * x;

递归函数出口：

• 在不断的二分之后，指数不断变小，最后变成零，此时就需要返回了，又因为零次方都是为 1，所以也就是 当指数为 0 的时候，返回 1 即可！

完整代码

class Solution {
public:
    double myPow(double x, int n) {
        long long count = abs(n); // n需要用长整型存储，不然在INT_MIN转为INT_MAX的时候会溢出

        if(n < 0)
            return 1 / dfs(x, count);
        return dfs(x, count);
    }

    double dfs(double x, long long count)
    {
        // 递归终止条件
        if(count == 0)
            return 1.0;
        
        // 快速幂的核心：对指数进行二分的形式处理
        // 进行后序遍历，拿到后面的结果，再对该结果进行处理，相当于对上面的二分又进行了归并！
        // 比如2^16，二分之后就是两个2^8，拿到2^8之后只需要让两者相乘就拿到了2^16
        // 但是要注意如果指数二分之后有余数的话，那么还需要再乘一次x，才不会遗漏
        double ret = dfs(x, count / 2);
        if(count % 2 == 0)
            return ret * ret;
        else 
            return ret * ret * x;
    }
};