先看代碼:
function fib(n){
if(n===1){
return 1;
}
if(n===2){
return 1;
}
if(n>2){
return fib(n-1)+fib(n-2);
}
}
console.log(fib(11));
這是一個很典型的利用遞歸計算斐波那契數(shù)列。
遞歸的缺點也是顯而易見的,我們計算fib(6)時 要計算fib(5)和fib(4)
而后計算fib(7)時,又要重復(fù)計算fib(6)與fib(5)
很明顯,我們之前已經(jīng)計算過了fib(6)與fib(5),現(xiàn)在重復(fù)計算,造成了浪費.
首先我們來觀察一下 當(dāng)n從20到21時,調(diào)用此函數(shù) 內(nèi)部會多調(diào)用多少次此函數(shù)?
var count=0;//計數(shù)器
function fib(n){
count++;
if(n===1){
return 1;
}
if(n===2){
return 1;
}
if(n>2){
return fib(n-1)+fib(n-2);
}
}
console.log(fib(20));
console.log(count);//13529次
count = 0;
console.log(fib(21));
console.log(count);//21891次 從20到21 調(diào)用次數(shù)增加不少
其實我們完全可以將之前計算過的數(shù)值用一個數(shù)組保存起來心例，如果需要重復(fù)計算闷旧，先去數(shù)組內(nèi)部查找，如果數(shù)組里面存在該結(jié)果，直接return
var cache = [0,1,1];
function fib(n){
if(n<=2){
return cache[n];
}else{
if(cache[n]){ //如果緩存數(shù)組中存在 直接返回
return cache[n];
}else{
var temp = fib(n-1)+fib(n-2); //如果緩存數(shù)組中不存在 進行遞歸
cache[n]=temp; //將遞歸結(jié)果存入緩存數(shù)組
return temp;
}
}
}
這樣已經(jīng)能夠節(jié)省很多遞歸造成的空間浪費了。
但是緩存數(shù)組孤零零的放在全局作用域，不夠安全旨指，封裝性也不好，比較寂寞喳整。
我們希望他們聯(lián)系的能夠更緊密一些谆构，就像一個整體。
于是有了下面的代碼：
var fib = (function(){
var cache = [0,1,1];
var fib = function() {
if(n<=2){
return cache[n];
}else{
if(cache[n]){ //如果緩存數(shù)組中存在 直接返回
return cache[n];
}else{
var temp = fib(n-1)+fib(n-2); //如果緩存數(shù)組中不存在 進行遞歸
cache[n]=temp; //將遞歸結(jié)果存入緩存數(shù)組
return temp;
}
}
}
return fib;
})()
這樣框都，我們通過閉包搬素，只能通過返回的fib方法對cache進行操作了。
當(dāng)然魏保，你也可以像下面這樣寫：
function createCache(){
var cache=[0,1,1];//緩存數(shù)組被封裝在閉包中,外界只能通過返回的方法進行操作
return function editCache(index,value){
if(value==undefined){
return cache[index];
}else{
cache[index]=value;
}
}
}
var fibCache=createCache();//創(chuàng)建緩存數(shù)組并且獲取接口方法
function fib(n){
if(n<=2){
return fibCache(n);
}else{
if(fibCache(n)){
return fibCache(n);
}else{
var temp = fib(n-1)+fib(n-2);
fibCache(n,temp);
return temp;
}
}
}
遞歸效率低是函數(shù)調(diào)用的開銷導(dǎo)致的熬尺。
在一個函數(shù)調(diào)用之前需要做許多工作，比如準(zhǔn)備函數(shù)內(nèi)局部變量使用的空間谓罗、搞定函數(shù)的參數(shù)等等粱哼，這些事情每次調(diào)用函數(shù)都需要做，因此會產(chǎn)生額外開銷導(dǎo)致遞歸效率偏低 來自知乎
其實一般遞歸的方法我們都可以通過迭代的方式來做檩咱，for循環(huán)就是一個很好的選擇：
function fib(n) {
if (n == 1 || n == 2) {
return 1;
}
var arr = [0,1,1];
for(var i = 2; i <= n; i++) {
arr[i] = arr[i-1] + arr[i-2];
}
return arr[n];
}
看起來也挺好的揭措，是吧。
下面進入算法時間税手，題目來自《劍指Offer》蜂筹，當(dāng)然需纳，遞歸依然是主角芦倒。
題目一：
一只青蛙一次可以跳上 1 級臺階，也可以跳上 2 級不翩。求該青蛙跳上一個 n 級的臺階總共有多少種跳法兵扬？
解題：數(shù)學(xué)歸納法。
1級臺階口蝠，1種跳法器钟，直接跳上1級臺階 f(1) = 1；
2級臺階妙蔗，2種跳法傲霸，直接跳上2級臺階或者連續(xù)跳兩次，每次一級 f(2) = 2；
3級臺階昙啄，如果第一次跳1級穆役，剩下2級臺階，f(2) = 2種跳法;如果第一次跳2級梳凛，剩下1級臺階耿币，f(1) = 1種跳法。f(3) = f(2) + f(1) = 2 + 1 = 3韧拒；
4級臺階淹接，如果第一次跳1級，剩下3級臺階叛溢，由上一條可知有3種跳法塑悼；如果第一次跳2級，剩下2級臺階雇初，由上上條可知有2種跳法拢肆，f(4) = f(3) + f(2) = 3 + 2 = 5；
n級臺階靖诗，f(n) = f(n-1) + f(n-2)
很熟悉對嗎郭怪？
function jump(n) {
if (n <= 0) {
return;
} else if (n > 0 && n <= 2) {
return n;
} else if (n > 2) {
return jump(n-1) + jump(n-2);
}
}
題目二：
一只青蛙一次可以跳上 1 級臺階，也可以跳上 2 級……它也可以跳上 n 級刊橘。求該青蛙跳上一個 n 級的臺階總共有多少種跳法鄙才？
解題：繼續(xù)歸納。
1級臺階促绵，1種跳法
2級臺階攒庵，2種跳法
3級臺階，4種跳法 f(3) = f(2) + f(1) + 1 = 4
4級臺階败晴，第一次跳1級浓冒，后面有f(3)種跳法，第一次跳2級尖坤，后面有f(2)種跳法稳懒，第一次跳3級，后面有f(1)種跳法慢味，第一次跳4級场梆，沒了
總共f(4) = f(3) + f(2) + f(1) + 1 = 8種跳法
5級臺階，f(5) = f(4) + f(3) + f(2) + f(1) + 1 = 16種跳法
歸納得纯路，f(n) = f(n-1) + f(n-2) + ... + f(1) + 1
function jump(n) {
if (n <= 0) {
return;
} else if (n > 0 && n <= 2) {
return n;
} else if (n > 2) {
var tmp = 0;
while(number > 1){
tmp+=jump(n-1);
number--;
}
return tmp+1;
}
}
