C语言力扣第50题之Pow（x，n），求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
• -104 <= xn <= 104

「快速幂算法」的本质是分治算法。举个例子，如果我们要计算 x^64，我们可以按照：

x→x2→x4→x8→x16→x32→x64

的顺序，从 x 开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到 x^{64} 的值，而不需要对 x 乘 63 次 x。

再举一个例子，如果我们要计算 x^{77}，我们可以按照：

x→x2→x4→x9→x19→x38→x77

的顺序，在 x→x2x \to x^2x→x2，x2→x4，x19→x38 这些步骤中，我们直接把上一次的结果进行平方，而在 x4→x9，x9→x19，x38→x77这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x。

直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。但如果我们从右往左看，分治的思想就十分明显了：

    当我们要计算 x^n 时，我们可以先递归地计算出 y=x⌊n/2⌋y = x^⌊n/2⌋，其中

    根据递归计算的结果，如果 n 为偶数，那么 x^n = y^2；如果 n 为奇数，那么 x^n = y^2×x；

    递归的边界为 n = 0，任意数的 0 次方均为 1。

由于每次递归都会使得指数减少一半，因此递归的层数为 O(log⁡n)，算法可以在很快的时间内得到结果。

double myPow(double x, int n){
    if (n == 0)
        return 1; // 递归出口
    if (n == 1)
        return x; // 递归出口
    // if (n < 0)
    //     return 1 / myPow(x, -n); // 此处n会越界
    if (n == -1)
        return 1 / x; // 只定义递归出口即可
    if (n % 2 != 0)
        return x * myPow(x, n - 1);
    else
        return myPow(x * x, n / 2);
}