前言

推出一個新系列，《看圖輕松理解數據結構和算法》，主要使用圖片來描述常見的數據結構和算法，輕松閱讀并理解掌握。本系列包括各種堆、各種隊列、各種列表、各種樹、各種圖、各種排序等等幾十篇的樣子。

斐波那契

斐波那契(Leonardo Pisano ,Fibonacci, Leonardo Bigollo，1175年-1250年)，又稱列奧納多，是中世紀意大利數學家。他是西方第一個研究斐波那契數列的人，并將現代書寫數和乘數的位值表示法系統引入歐洲。主要作品包括《計算之書》、《幾何實踐》、《平方數書》等。

斐波那契數列

斐波那契數列，又稱黃金分割數列或兔子數列，該數列為0、1、1、2、3、5、8、13、21、34、…，可以看到它的性質是前兩項之和等于后一項。

兔子問題

斐波那契數列可以用來描述兔子繁殖問題，一般而言，兔子在出生兩個月后就有繁殖能力，一對兔子每個月能生出一對小兔子。如果所有兔子都不死，那么一年后可以繁殖多少對兔子？實際結果如下，第一個月和第二個月，兔子還沒有繁殖能力，所以都只有1對。第三個月生下第一對，總共有2對。第四個月老兔子繼續生下一對，另一對還沒有繁殖能力，總共有3對。以此類推，第五個月到第十二個月的兔子對數對應如下。

表達式

image

遞歸實現

int fib(int n){
 if (n == 0)
 return 0;
 if (n == 1)
 return 1;
 return fib(n - 1) + fib(n - 2);
}

假如n=4時，看看遞歸過程的堆棧情況。

① 調用fib函數，傳入參數值4。

image

② fib(4)=fib(3)+fib(2)，需要繼續調用fib(3)，而fib(2)先不進入執行堆棧。

image

③ fib(3)=fib(2)+fib(1)，需要繼續調用fib(2)，fib(1)先不進入執行堆棧。

image

④ fib(2)=fib(1)+fib(0)，需要繼續調用fib(1)，fib(0)先不進入執行堆棧。

image

⑤ fib(1)返回1，停止往下調用，然后上一步的fib(0)進入堆棧。

image

fib(0)返回0，則 ④ 中的fib(2)=fib(1)+fib(0)=1

image

image

然后，堆棧回到③中，因為fib(3)=fib(2)+fib(1)，所以將fib(1)入棧。

image

fib(1)返回1，則 ③ 中的fib(3)=fib(2)+fib(1)=1+1=2。

image

image

然后，堆棧回到 ② 中，因為fib(4)=fib(3)+fib(2)，所以將fib(2)入棧。而fib(2)=fib(1)+fib(0)，于是將fib(1)入棧。此時fib(1)直接返回1，然后繼續將fib(0)入棧。則fib(2)=fib(1)+fib(0)=1，最后fib(4)=fib(3)+fib(2)=3。

image

image

image

image

image