[leetcode]No.50 实现一个 Pow(x, n)

[liangbus]

No.50 实现 pow(x, n) ，即计算 x 的 n 次幂函数。

这题看起来不难，于是就写了
简单版本

var myPow = function(x, n) {
    if(n === 0) return 1
    let res = 1
    let posN = Math.abs(n)
    while(posN-- > 0) {
        res *= x
    }
    return n > 0 ? res : 1 / res
};

这个简单版其实已经正确已经跑通了大多数用例了，只是有几个特殊的边界没有考虑到，导致超时
我们来进一步优化它

上面我们是通过一个循环一个个去乘，这样会比较低效率，回想我们学过的数学知识，幂运算

幂运算（指数运算）是一种关于幂的数学运算。同底数幂相乘，底数不变，指数相加；同底数幂相除，底数不变，指数相减。幂的幂，底数不变，指数相乘。

因此，我们可以通过递归的方式实现

var myPow = function(x, n) {
    if(n < 0) return 1 / powHelper(x, -n)
    return powHelper(x, n)
};
function powHelper(x, n) {
    if(n === 0) return 1
    // 指数为奇数的，要拆一个出来，再将其折半
    return n % 2 !== 0 ? powHelper(x*x, (n -1) /2) * x : powHelper(x*x, n/2)
}