LeetCode题解：50. Pow(x, n)，递归分治，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/powx-n/

解题思路：

1. x的n次幂可以分解为x的n/2次幂的平方。
2. 按照步骤1的思路，通过递归逐级分解，时间复杂度即为O(logn)。
3. 如果n为负，问题可以转换为计算1除以x的n次幂。

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  // 0和1的n次幂都是其本身
  if (x === 1 || x === 0) {
    return x;
  }
  // -1的奇数幂等于-1
  // -1的偶数幂等于1
  if (x === -1) {
    return n % 2 ? -1 : 1;
  }
  // 递归终止条件
  // x的0次幂是1
  if (n === 0) {
    return 1;
  }

  // n > 0时，正常计算n次幂
  if (n > 0) {
    // n次幂等于n/2次幂的平方
    // 如果n为奇数，则需要再乘以x
    const res = myPow(x, Math.floor(n / 2));
    return n % 2 ? res * res * x : res * res;
  } else {
    // n < 0时，将问题转换为计算1/x^n
    return 1 / myPow(x, -n);
  }
};