剑指 Offer 16. 数值的整数次方

一、题目描述

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

二、思考过程

第一版：我是用的简单地每次都乘以该数，然后递归，每次都乘一次，这样绝对是能算出来的，但是在n非常大的时候，并且系统不支持尾递归优化的话，那么就会超时，栈溢出。

var myPow = function(x, n) {
    if(n < 0) {
        x = 1 / x;
        n = -n;
    }
    function pow(k, n) {
        if(n == 0) return 1;
        if(n == 1) return k;
        return pow(k * x, n - 1);
    }
    return pow(x, n);
};

第二版：想到了快速幂，思路是当每次都取上一次结果的平方，同时记录的变量c也乘以2，当某次乘以2的时候大于了n，那么就不使用pow了，使用pow2，也就是方法一中的代码，把剩下的n-c的部分补回来。这一版相比于第一版改进了不少，但是还是存在栈溢出的问题，这个问题是因为当n很大的时候，并且n/2也非常大，那么相对于第一版也是没有优化的。

var myPow = function(x, n) {
    if(n < 0) {
        x = 1 / x;
        n = -n;
    }
    function pow(k, c) {
        if(c == 0) return 1;
        if(c == n) return k;
        if(c * 2 > n) {
            return pow2(k, n - c + 1);
        }
        return pow(k * k, c * 2);
    }
    function pow2(k, c) {
        if(c == 0) return 1;
        if(c == 1) return k;
        return pow2(k * x, c - 1);
    }
    return pow(x, 1);
};

第三版：既然剩下的部分也很大，那么直接将剩下的部分继续快速幂，这一版最终通过了。

var myPow = function(x, n) {
    if(n < 0) {
        x = 1 / x;
        n = -n;
    }
    function pow(k, c) {
        if(n == 0) return 1;
        if(c == n) return k;
        if(c * 2 > n) {
            n = n - c;
            return k * pow(x, 1);
        }
        return pow(k * k, c * 2);
    }
    return pow(x, 1);
};

第四版：这是力扣上大神的做法，对于递归有着很深入的理解，边界值分为0、1、-1、通过n递归除以2，能最终取到1或-1，half代表x的n/2次幂，那么half*half就是完整的n次幂，如果没有余数，那么就是最终结果，如果有余数那么乘以余数就是最终结果。

var myPow = function(x, n) {
    if(n == 0) return 1;
    if(n == 1) return x;
    if(n == -1) return 1 / x;
    let half = myPow(x, ~~(n / 2));
    let mod = myPow(x, n % 2);
    return half * half * mod;
}