??????? 前置文章：遞歸算法：www.itdecent.cn/p/703069f3ba3f .
??????? 雖然我說遞歸算法算得上是一種底層的算法，但是遞歸算法的應(yīng)用很廣泛的。
??? 遞歸算法的一個經(jīng)典應(yīng)用是Fibonacci數(shù)列（斐波那契數(shù)列），我為數(shù)不多的非常喜歡的一個數(shù)列。Fibonacci數(shù)列的定義是這么說的：斐波那契數(shù)列的每一項(xiàng)都等于前兩項(xiàng)之和（明顯第一項(xiàng)和第二項(xiàng)是特殊項(xiàng)）。
??? 斐波那契的概念非常容易理解。打個比方，我現(xiàn)在手里有一片蘋果林，我這蘋果林每年都會生產(chǎn)很多的蘋果，我拿這蘋果干嘛呢，我這蘋果不吃，我也不賣，我用來喂兔子，我養(yǎng)兔子。我養(yǎng)這兔子跟吃蘋果不一樣，我這兔子第一年出生，然后長一年，第二年開始能進(jìn)行生殖，一年一次，一次一窩，一窩一個。
??????????? 我今年就抱著一堆蘋果去我鄰居那換了個兔崽子，我還給它起了個名，叫兔一，第一年我有一只兔子。? F(1) = 1.
??????????? 兔一今年長一年，然后第二年，兔一生了一個兔子，我叫它兔二，第二年我有倆兔子，成熟得兔一和還是崽子的兔二。 F(2) = 2.
??????????? 第三年，兔一生一個兔子，叫兔三，兔二長大成兔，我這第三年就有了三只兔子，兔一二三。 F(3) =F(1)+F(2) = 1+2 = 3.
??????????? 第四年，兔一、兔二都生了一只，叫兔四、兔五，然后兔三長大了。說到這，有種葫蘆娃的感覺是吧，我這兔老大、老二、老三都有了，然后一下出來了兔四五。然后這兔子現(xiàn)在又多了，我現(xiàn)在五只兔子。 F(4) = F(2) + F(3) = 2+3 = 5.
??????????? 第五年，兔一二三都開始生兔子了，然后兔四五長大了，我又多了三只兔子，兔六七八。我現(xiàn)在有了八只兔子了。F(5) = F(4) + F(3) = 5+3 = 8.
??????????? 第六年，我這兔子就非?？捎^了，我有8+5=13只兔子。說到這里，已經(jīng)非常明白了，我這里兔子是一年熟，然后開始生殖的，也就是隔年生。那我今年擁有的兔子就是我去年有的兔子和我前一年有的兔子之和，因?yàn)榍澳甑耐米硬还艽笮?，今年一定能生，生下來的就是凈增長。所以，我這兔子就能推出一個公式：F(n) = F(n-1)+ F(n-2) (n>=2).
??? 我這養(yǎng)兔子的過程就是一個典型的斐波那契數(shù)列的問題，一個遞推的問題，這個題目也是斐波那契數(shù)列的典型應(yīng)用。而遞歸要求的基準(zhǔn)情形，也就是遞歸出口：我兔子養(yǎng)的太多了，我蘋果不夠了，那我就不繼續(xù)養(yǎng)兔子，我可能是把它們賣了，或者是送人，那這個遞歸就結(jié)束了。
?? 用兔子來講斐波那契數(shù)列非常清晰明了了。斐波那契數(shù)列的遞推算法也就有了：
int fib[50];
void fibonacci(int n) {
??????? fib[0] = 1;
??????? fib[1] = 1;
??????? for( int i=2; i<=n; i++){
??????????????? fib[i] = fib[i-1] + fib[i-2];
??????? }
}
??? 我說我很喜歡斐波那契數(shù)列，不僅僅是因?yàn)殪巢瞧鯏?shù)列在算法應(yīng)用上簡單并且實(shí)用性廣，而是因?yàn)椋巢瞧鯏?shù)列的美，數(shù)學(xué)美，藝術(shù)美：
??? 斐波那契數(shù)列的數(shù)學(xué)美是美在：數(shù)列中的每前后兩項(xiàng)做的比值，也就是F(n-1)/F(n) ，隨著斐波那契數(shù)列數(shù)值的增長，比值趨近于黃金分割線，也就是0.618。而斐波那契數(shù)列的藝術(shù)美是美在：
??? 斐波那契螺旋曲線！！！多么令人驚艷的數(shù)學(xué)圖形。
??? 完美的斐波那契，真正的演算公式或者算法公式卻僅僅用幾行文字就能表達(dá)出來，如我所說：
