終于來到了有點意思的地方——遞歸，在我最開始學習js的時候，基礎課程的内容就包括遞歸，但是當時并不知道遞歸的真正意義和用處。我隻是知道，哦...遞歸是自身調用自身，遞歸要記得有一個停止調用的條件。那時，我還不了解遞歸的内在含義，好在現在知道了一點。
有些問題的本身就是遞歸的，我們想一個程式問題，也是比較經典的面試問題——有一個對象a，我們不知道它有多少層級，如何複制對這個對象?你可能會說，直接聲明一個變量var b = a不就可以了嘛？但是，如果我改動了a中的一個屬性，b中的屬性也跟着改變了。因為你隻是将b得到指針指向了a，并沒有開辟一塊新的空間來存儲“存儲在a中的屬性”。也就是我們所謂的淺拷貝。那麼如何改變a中的屬性，b的屬性還是原來的樣子呢？我們可以利用遞歸來解決這樣的問題。
我記得前面的文章（
用js來實作那些資料結構05（棧02-棧的應用））例舉了用棧解決問題的執行個體。其中最後一個問題是漢諾塔問題，也需要用遞歸來解決。那麼就漢諾塔問題來說，如果不用遞歸，是否還有其它的可行的算法得以解決這樣的問題呢？
很多人會覺得遞歸是低效率的，隻不過是因為人腦的有限性不得不讓計算機去更忙碌一點，其實這種想法實在是片面的。因為有些問題本身就是遞歸的，比如我們上面所舉例子。再比如，有些問題或許可以遞歸，可以循環，還可以用其他方法來解決，但是遞歸更容易讓我們的代碼簡潔易懂，于是我們選擇了遞歸。
好了，說了很多，我們還是回到遞歸本身吧，遞歸說到底是一種解決問題的方法，它解決問題的各個小部分，直到解決最初的大問題。那麼，遞歸通常都會調用自身，就像下面這樣：
function a() {
a();
} 當然，這樣寫也是一樣的：
function a() {
b();
}
function b() {
a();
} 當然，上面代碼隻是舉個例子，沒有什麼實際意義。
在我們在最開始試着去實作一個遞歸的時候，往往會出現stack overflow error等類似棧溢出的錯誤。因為我們的遞歸無限的執行下去以至于浏覽器不得不強制停止遞歸，然後告訴你，出錯了。我們可以寫一點簡單的代碼來測試一下：
var i = 0;
function recursiveFn() {
i++;
recursiveFn();
}
try{
recursiveFn();
} catch(err) {
console.log(i,"error is:" + err);
}
// Google
//15710 "error is:RangeError: Maximum call stack size exceeded"
// FireFox
//65657 error is:InternalError: too much recursion
//QQ
// 41756 "error is:RangeError: Maximum call stack size exceeded"
//ie
//8225 error is:Error: 堆棧溢出
//edge
// 15466 error is:Error: Out of stack space 我們發現似乎每一個浏覽器，棧溢出的上限都是不一樣的。因為每一種浏覽器廠商都為其自己的浏覽器設定了不同的限度。甚至包括一些js原生api的内部實作方式，在不同的浏覽器上都是不一樣的。
我們發現遞歸是如此的簡單，就是自身調用自身，再加一個限制條件，就可以實作遞歸了。上面我們所寫的代碼在一定程度上隻是為了解釋遞歸這個概念。沒有太多的實際意義。那麼，下面我們看看用遞歸來解決
斐波那契數列問題。
那麼我們先來看這樣一個問題，經典的
兔子繁殖問題。一般而言，兔子在出生兩個月後，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔子都不死，那麼一年以後可以繁殖多少對兔子？
我們不妨拿新出生的一對小兔子分析一下：第一個月小兔子沒有繁殖能力，是以還是一對，兩個月後，生下一對小兔，對數共有兩對，三個月以後，老兔子又生下一對，因為小兔子還沒有繁殖能力，是以一共是三對。依次類推：
這就是斐波那契數列了，在生活中，也有許多斐波那契數列存在的地方。
那麼我們可以提取一下：1和2的斐波那契數是1，3的斐波那契數是2，4的斐波那契數是3。換句話說，在n>2的情況下，F(n) = F(n-1) + F(n - 2)——這裡的n代表着在斐波那契數列中的第幾個斐波那契數。那麼，我們再用語言描述一下——除開最開始的兩項以外，以後的每一項都是前兩項的和，這就是我們的遞歸體和遞歸終止條件，我們來看下代碼：
function fibonacci(num) {
if(num === 1 || num === 2) {
return 1;
}
return fibonacci(num - 1) + fibonacci(num - 2);
}
console.log(fibonacci(6)) 要注意，不要試超過50的數噢，因為越往後相加的計算量就會越來越巨大。那麼我們畫個圖來看看，我們遞歸算出第6項的斐波那契數時，遞歸是如何進行的：
我們看上圖一步一步的解釋：
每一個方塊中“/”後面的是目前調用的計算結果。我們從第一次fib(6)開始，由于6既不是1也不是2是以停止條件不符合，我們直接return了兩次調用但是這兩次調用又對num參數做了減一和減二的操作。是以就到了下一層。直到最後每一層的調用都執行到了num=1或者num=2的情況時。遞歸最終終止。那麼，在遞歸終止的時候，結果是由遞歸到最底層條件一點一點向上傳回的。是以，遞歸的執行時由上至下但是遞歸結果的傳回則是由下至上的。這樣我們就完成了一次整個遞歸的過程。
最後，由于本人水準有限，能力與大神仍相差甚遠，若有錯誤或不明之處，還望大家不吝賜教指正。非常感謝！
一隻想要飛得更高的小菜鳥