50. Pow(x,n)

Pow(x, n)就是求x的n次幂，当然我们可以直接使用库函数，但是这样的话，你的面试要凉凉了。

第一种思路：暴力求解法。一层循环累乘即可。

第二种思路：分治&递归。x的n（偶数）次方可以分解为两个x的n/2次方，如果是奇数的时候就首先单独提一个x出来，这样就可以把n变为偶数了。终止条件自然是n=1的时候。同时要考虑下n<0时候的一些转换。

// 递归版本
function myPow(x, n) {
    if(n < 0) {
        return 1 / myPow(x, -n);
    }
    if( n === 0 ) return 1;
    if( n === 1) return x;

   // 如果n为奇数
    if(n % 2) return x * myPow(x, n -1);

    // 其余就都是偶数情况
    return myPow(x * x, n / 2);
}

// 非递归版本
function myPow(x, n) {
    if(n < 0) {
        n = -n;
        x = 1 / x;
    }
    if(n === 0) return 1;
    if(n === 1) return x;

    let pow = 1;

    while(n) {
        // 如果n为奇数, 先单独乘一个x
        if(n % 2) {
            pow = pow * x;
            n = n - 1;  // 提出去后，自然把n减去一个
        }
        // 剩余都是偶数情况
        x = x * x;
        n = n / 2;
    }

    return pow;
}