這節課試圖了解一下 斐波那契（Fibonacci）數列（黃金分割數列）的遞歸實現，作為一個例子。

斐波那契（Fibonacci）數列的腦補鏈接

斐波那契提出一個著名的兔子繁殖問題：

如果一對兔子每月能生一對小兔（一雄一雌），而每對小兔在它出生后的第三個月里，又能開始生一對小兔，假定在不發生死亡的情況下，由一對出生的小兔開始，50個月后會有多少對兔子？

在第一個月時，只有一對小兔子，過了一個月，那對兔子成熟了，在第三個月時便生下一對小兔子，這時有兩對兔子。再過多一個月，成熟的兔子再生一對小兔子，而另一對小兔子長大，有三對小兔子。如此推算下去，我們便發現一個規律（表格省略）：

由此可知，從第一個月開始以后每個月的兔子總數是：1,1,2,3,5,8,13,21,34,55,89,144,233...。若把上述數列繼續寫下去，得到的數列便稱為斐波那契數列。數列中每個數便是前兩個數之和，而數列的最初兩個數都是1。

用文字來說，就是費波那契數列由0和1開始，之后的費波那契系數就由之前的兩數相加。首幾個費波那契系數是（OEIS A000045）：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，………………

特別指出：0不是第一項，而是第零項。——《維基百科》

斐波那契（Fibonacci）數列的迭代實現：

先用數學函數來定義

f(n) :

當n=1 f(n)=1

當n=2 f(n)=1

當n=3 f(n)=2

當n=4 f(n)=3

…

推理：n>2時數列可表達為： f(n)=f(n-1) + f(n-2) 

練習：假設我們需要求出經歷了20個月后，總共有多少對小兔崽子

普通迭代寫法：（實在不會寫！！！不知是數學盲還是腦殘。。。。）

#知道邏輯但不會寫代碼，打擊太大了。。def fab(n):    n1 = 1        #第一個月1    n2 = 1        #第二個月1    n3 = 1        #第三個月開始，初始化為1        if n < 1:        #判斷如果月份小于一那就沒意義了。設置返回一個 -1 的錯誤，供后面調用        PRint('輸入有誤')       return -1        while (n-2) > 0:       n3 = n2 + n1    #從第三個月開始，第三個月等于第二個月和第一個月之和，賦值給n3       n1 = n2    #那么第一個月就等于現在的第二個月，也就是n2的值重新賦值給第一個月            n2 = n3    #同理，第二個月等于現在的第三個月，用n3的值重新賦值給第二個月        n -= 1    # 重新賦值之后，循環次數-1            return n3    #返回結果result = fab(20)if result != -1:    print(‘總共有%d對小兔崽子誕生’ % result)

個人理解：迭代需要一個初始值，那么這里給了第一個月和第二個月的初始值，第三個月是前兩個月相加，那么第三個月也有一個初始值，也就是2，當月份變化時，每一個迭代都會重新賦值，也就是說也有三個初始值，一個是當前月的值n3，一個是當前月-1的值即n2，還一個是當前月-2的值，即n1，那么n3就是最后要求的結果。

遞歸寫法：

#Fibonacci數列遞歸寫法：def fab(n):#判斷n如果小于1返回錯誤信息    if n < 1:        print('輸入有誤！')        return - 1# 如果沒有下面這條if件句，程序將陷入死循環，為什么？？？？？？    if n == 1 or n == 2:        return 1    else:        return fab(n-1) + fab(n-2)result = fab(20)if result != -1:    print('總共有%d對小兔子誕生' % result)#我嘗試用def fab(n):    return fab(n-1) + fab(n-2)print(fab(20))#結果返回一個死循環。#為什么要加上條件語句？如果單單是判斷n<2的話，我賦給函數fab(20)，并不小于2，

#腦子實在轉不過彎來。求明示！！！！！

遞歸的中心思想就是 分治思想！一個大問題解決不了，那么可以把大問題分解成若干小問題，把若干小問題解決了，那么大問題也就解決了。

但遞歸也有其缺陷，比如把上面的20改為35，然后運行它，結果發現，遞歸算法要等那么一秒鐘才算出來，如果用迭代，那么結果就是秒出。所以遞歸要用在適當的位置適當的時機。