一役电、題目描述
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次方棉胀。不得使用庫(kù)函數(shù)法瑟，同時(shí)不需要考慮大數(shù)問(wèn)題。
示例 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
說(shuō)明:
-100.0 < x < 100.0
n 是 32 位有符號(hào)整數(shù)唁奢，其數(shù)值范圍是 [?231, 231 ? 1] 霎挟。
二、思考過(guò)程
第一版：我是用的簡(jiǎn)單地每次都乘以該數(shù)麻掸，然后遞歸酥夭，每次都乘一次，這樣絕對(duì)是能算出來(lái)的，但是在n非常大的時(shí)候采郎，并且系統(tǒng)不支持尾遞歸優(yōu)化的話千所，那么就會(huì)超時(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ǔ)回來(lái)犯建。這一版相比于第一版改進(jìn)了不少讲冠，但是還是存在棧溢出的問(wèn)題，這個(gè)問(wèn)題是因?yàn)楫?dāng)n很大的時(shí)候适瓦，并且n/2也非常大竿开，那么相對(duì)于第一版也是沒有優(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ù)快速冪否彩，這一版最終通過(guò)了。
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);
};
第四版：這是力扣上大神的做法嗦随，對(duì)于遞歸有著很深入的理解列荔，邊界值分為0、1枚尼、-1贴浙、通過(guò)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;
}
