Python中斐波那契數列

今天我們來說說一幫小兔子 。

按理來說，今天的話題與兔子不搭邊。 所以本節就講講如何用遞歸實現斐波那契數列。

斐波那契數列的發明者，是義大利數學家列昂納多*斐波那契(Leomuado Fibonacci)。

當年這個數列是由兔子交配的故事開始講起的：假如說兔子在出生兩個月後，就有了繁殖能力，此後這對兔子在接下來的每個月都能生出一對可愛的小兔子。假設所有兔子都不會老去，就這麼一直折騰下去，那麼一年以後可以繁殖多少對免子出來呢？

我們都知道兔子繁殖能力是驚人的：

假設需要求出經歷了 20個月後，總共有多少對小兔子，不妨考慮一下分別用迭代和遞歸如何實現？

迭代實現：

def fab(n):

a1 = 1

a2 = 1

a3 = 1

if n < 1:

print('輸入有誤！')

return -1

while (n-2) > 0:

a3 = a1 + a2

a1 = a2

a2 = a3

n －= 1

return a3

result = fab(20)

if result != -1:

print('總共有%d對小兔子誕生!'， % result)

遞歸實現：

def fab(n):

if n < 1:

print（'輸入有誤！'）

return -1

if n == 1 or n == 2:

return 1

else:

return fab(n-1) + fab(n-2)

result = fab(20)

if result != -1:

可見邏輯非常簡單，直接把所想的東西寫成代碼就是遞歸算法了。不過，之前總說遞歸如果使用不當，效率會很低，但是有多低呢？這就來證明一下。我們試圖把20個月修改為35個月，然後試試看把程序執行起來。發現了吧，用迭代代碼來實現基本是毫秒級的，而用遞歸來實現就考驗你的CPU能力啦（N秒~N分鐘不等）。這就是小甲魚不支持大家所有東西都用遞歸求解的原因，本來好好的一個代碼，用了遞歸，效率反而拉下了一大截。

如果不懂得遞歸，試圖想要寫個程序來解決問題是相當困難的，但如果使用了遞歸，你會發現問題奇蹟般地變簡單了！