Python 中的斐波那契數列

斐波那契數列從 F0 = 0 和 F1 = 1 開始。之後每一項都是前兩項的總和：Fn = Fn-1 + Fn-2。採用從 0 開始的索引時，數列的前幾項為 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233。若要產生數列，請先確認輸入代表項數還是索引；除非另有說明，下方範例中的輸入都是項數。

使用迴圈產生斐波那契數列

需要前 n 項時，迴圈是實用的預設選擇。它需要 O(n) 時間，並且只用前兩個值作為輔助狀態。回傳的串列本身需要 O(n) 輸出空間；當 n = 1 時，串列內容為 [0]。

執行下方範例：

本節中的程式碼以及顯示的標籤或輸出仍為英文。

def fibonacci_sequence(n):
    terms = []
    a, b = 0, 1
    for _ in range(max(0, n)):
        terms.append(a)
        a, b = b, a + b
    return terms


print(fibonacci_sequence(10))

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

每次迭代都會先附加目前的值，再更新這一對數值。這個順序能讓 F0 保持為第一項，並使結果串列的長度符合要求的項數。Python 整數可以超出固定寬度的機器整數範圍，因此即使數值變大，仍可精確取得各項；不過，數值越大，運算所需時間也越長。

使用遞迴計算斐波那契數

直接遞迴會依照定義計算：若要計算 Fn，函式會分別呼叫自身計算 Fn-1 和 Fn-2。下方的簡單版本適合用來理解遞迴關係，但會重複進行許多相同的計算。它的執行時間呈指數級增長，而且呼叫層數很深時也會占用直譯器的呼叫堆疊。此函式只接受標準數列中從 0 開始的索引；索引小於 0 時會引發 ValueError。若要計算較大的索引，請改用迴圈或儲存計算結果的方法。

本節中的程式碼以及顯示的標籤或輸出仍為英文。

def fibonacci_recursive(n):
    if n < 0:
        raise ValueError("n must be a nonnegative index")
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


print([fibonacci_recursive(i) for i in range(10)])

此處的引數代表索引，而非項數：串列生成式會依序計算 F0 到 F9。基底情況會直接回傳起始值。

使用動態規劃產生斐波那契數列

動態規劃會儲存計算結果，讓每一項只計算一次。當 n <= 0 時，函式會回傳 []；否則，這個使用串列的版本需要 O(n) 時間和 O(n) 總空間，其中包含回傳的串列。上方的迴圈在回傳串列時也需要 O(n) 總空間，但除了輸出以外，僅使用 O(1) 輔助空間。如果只需要最後一項，使用兩個變數的迭代計算可以將總空間降至 O(1)。

本節中的程式碼以及顯示的標籤或輸出仍為英文。

def fibonacci_dynamic(n):
    if n <= 0:
        return []
    if n == 1:
        return [0]

    terms = [0, 1]
    for i in range(2, n):
        terms.append(terms[i - 1] + terms[i - 2])
    return terms


print(fibonacci_dynamic(10))

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

更新方式與迴圈使用相同的遞迴關係，而串列則會保留先前各項。若後續操作需要存取整個數列中的較早項目，請選擇這種方法。若希望用簡單的一輪迭代產生數列，且只使用常數輔助空間，則可選擇回傳串列的迴圈；但回傳的串列仍需要 O(n) 空間。若只需要某個索引對應的單一數值，則可用兩個變數的迴圈，避免儲存整個數列。

使用比內公式計算斐波那契數

比內公式可利用冪次與黃金比例 φ = (1 + √5) / 2，直接表示從 0 開始索引的斐波那契數：

Fn = (φⁿ - ((1 - √5) / 2)ⁿ) / √5

直接以 Python 實作時，可以使用 math.sqrt，但浮點數運算只能近似表示這些無理數。因此，索引夠大時，四捨五入可能會造成結果差 1。這個公式適合用來理解閉式解或估算數值；若需要精確的整數結果，請優先使用迴圈或動態規劃。

本節中的程式碼以及顯示的標籤或輸出仍為英文。

from math import sqrt


def fibonacci_binet(n):
    phi = (1 + sqrt(5)) / 2
    psi = (1 - sqrt(5)) / 2
    return round((phi ** n - psi ** n) / sqrt(5))


print([fibonacci_binet(i) for i in range(10)])

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]