快速幂+递归
1.原理
快速幂算法的本质是分治算法。举个例子，如果我们要计算 x^64，我们可以按照：
的顺序，从 x 开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到 x^64的值，而不需要对 x 乘 63 次 x 。
再举一个例子，如果我们要计算 x^77，我们可以按照：
的顺序，在 x → x^2, x^2 → x^4, x^19 → x^38这些步骤中，我们直接把上一次的结果进行平方，而在 x^4 → x^9, x^9 → x^19, x^38 → x^77这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x。
直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。但如果我们从右往左看，分治的思想就十分明显了：
- 当我们要计算 x^n时，我们可以先递归地计算出 y = x^[[n/2] ，其中[n/2]表示对 [n/2] 进行向下取整；
- 根据递归计算的结果，如果 n 为偶数，那么 x^n = y^2 ；如果 n 为奇数，那么 x^n = y^2 * x
- 递归的边界为 n = 0，任意数的 0 次方均为 1。
由于每次递归都会使得指数减少一半，因此递归的层数为 O(log n)，算法可以在很快的时间内得到结果。
2.LeetCode 50: Pow(x, n)
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即x^n）。
示例 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的n次幂，采用暴力法，时间复杂度为O(n)，当n过大时，会超时，因此采用快速幂是一个很好的选择，其复杂度为O(log n)。
- 当指数 n 为负数时，我们可以计算 x^[[-n] ，再取倒数得到结果，因此我们只需要考虑 n 为自然数的情况。
代码如下：
function quickMul(x, n) {
if (n === 0) return 1
const y = quickMul(x, Math.floor(n/2))
return n % 2 === 0 ? y * y : y * y * x
}
var myPow = function (x, n) {
if (n > 0 || n === 0) return quickMul(x, n)
else return 1/quickMul(x, -n)
};