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]