Python實作斐波那契數列

1.斐波那契數列背景知識

斐波那契數列指的是這樣一個數列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368…

這個數列從第3項開始，每一項都等于前兩項之和。

斐波那契數列的定義者，是意大利數學家列昂納多·斐波那契（Leonardo Fibonacci）

2.斐波那契數列的遞推公式和通項公式

斐波那契數列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
           

如果設F(n）為該數列的第n項（n∈N*），那麼這句話可以寫成如下形式：:F(n)=F(n-1)+F(n-2)，F(1)=F(2)=1。

通項公式如上。

3.python程式實作。

3.1.1 遞歸函數

def fib(n):
    if n < 3:
        return 1
    else:
        return fib(n-1) + fib(n-2)
           

在python中，當使用遞歸形式時，需要注意的時，當使用python寫的遞歸程式如果遞歸太深, 那麼極有可能因為超過系統預設的遞歸深度限制而出現錯誤。一般預設遞歸長度在1000左右。

RecursionError: maximum recursion depth exceeded in comparison
           

3.1.2 棧溢出

在Python中，函數調用是通過棧（stack）這種資料結構實作的，每當進入一個函數調用，棧就會加一層棧幀，每當函數傳回，棧就會減一層棧幀。由于棧的大小不是無限的，是以，遞歸調用的次數過多，會導緻棧溢出。

解決遞歸調用棧溢出的方法是通過尾遞歸優化，事實上尾遞歸和循環的效果是一樣的，是以，把循環看成是一種特殊的尾遞歸函數也是可以的。

尾遞歸是指，在函數傳回的時候，調用自身本身，并且，return語句不能包含表達式。這樣，編譯器或者解釋器就可以把尾遞歸做優化，使遞歸本身無論調用多少次，都隻占用一個棧幀，不會出現棧溢出的情況。

代碼實作：

def fib(n,res=0,tmp=1):
	if n== 0:
	    return res
	return fib(n-1,tmp, res+tmp)
           

例如：fib(5) = = > fib(4, 1, 1) = => fib(3, 1 , 2) = = > fib(2 , 2 ,3) = = >fib(1, 3, 5)

= => fib(0, 5,8) = => 5

這裡需要注意的是，函數内部，是按照命名參數傳值的。但是當執行時，傳參時按位置參數來指派的。尾遞歸優化，按照我個人了解，就是将需要遞歸計算的值通過函數的參數來實作。不在函數内部通過表達式實作。以此來實作尾遞歸的優化。

或者我們可以手動來設定，

import sys
sys.setrecursionlimit(1000000) #括号中的值為遞歸深度
           

但是當我設定了之後，這個數字是非常大的。運作結果出來的也非常慢。

3.2 for循環

def fib(n):
	    f1 = f2 = 1
    for k in range(1, n-1):
        f1, f2 = f2, f2 + f1
    return f2
           

當然while循環同樣可以實作上述的函數定義。

3.3 通項公式

def fib2(n):
    a = (1 + math.sqrt(5)) / 2
    b = (1 - math.sqrt(5)) / 2
    num_n = (1 / math.sqrt(5)) * (a ** n - b ** n)
    return int(num_n)
           

這種通項公式的寫法複雜。而且需要對浮點型資料進行資料轉換。同樣會出現棧溢出的情況。

以上資料大部分來自于，和自己的一點整理。如有錯誤，煩請回複更正。