一、題目描述

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
實(shí)現(xiàn)函數(shù)double Power(double base, int exponent)，求base的exponent次方。不得使用庫函數(shù)，同時(shí)不需要考慮大數(shù)問題。

示例 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 位有符號整數(shù)，其數(shù)值范圍是 [?231, 231 ? 1] 。

二、思考過程

第一版：我是用的簡單地每次都乘以該數(shù)，然后遞歸，每次都乘一次，這樣絕對是能算出來的，但是在n非常大的時(shí)候，并且系統(tǒng)不支持尾遞歸優(yōu)化的話，那么就會超時(shí)，棧溢出。

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);
};

第二版：想到了快速冪，思路是當(dāng)每次都取上一次結(jié)果的平方，同時(shí)記錄的變量c也乘以2，當(dāng)某次乘以2的時(shí)候大于了n，那么就不使用pow了，使用pow2，也就是方法一中的代碼，把剩下的n-c的部分補(bǔ)回來。這一版相比于第一版改進(jìn)了不少，但是還是存在棧溢出的問題，這個(gè)問題是因?yàn)楫?dāng)n很大的時(shí)候，并且n/2也非常大，那么相對于第一版也是沒有優(yōu)化的。

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);
};

第三版：既然剩下的部分也很大，那么直接將剩下的部分繼續(xù)快速冪，這一版最終通過了。

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次冪，如果沒有余數(shù)，那么就是最終結(jié)果，如果有余數(shù)那么乘以余數(shù)就是最終結(jié)果。

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;
}