python3实现斐波那契数列(4种方法)

本文将介绍 4 种 Python3 实现斐波那契数列的方法，分别是递归法、递推法、生成器、矩阵法，让读者了解并掌握其中的实现方法。

1. 递归法

递归法非常简单，只需要按照斐波那契数列的定义进行递归求解即可。

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

需要注意的是，递归法的时间复杂度和空间复杂度都非常高，因为每次计算都要重复计算很多次相同的数值，因此不推荐使用。

2. 递推法

递推法用循环代替递归，通过两个变量存储中间结果，利用前面的结果递推后面的结果。

def fib_iterative(n):
    if n < 2:
        return n
    else:
        a, b = 0, 1
        for i in range(n-1):
            a, b = b, a+b
        return b

递推法的时间复杂度是线性的（O(n)），空间复杂度是常数级的（O(1)），是比较优秀的算法实现。

3. 生成器

生成器是 Python 的一种特殊函数，用于迭代数据的生成，可以用于实现斐波那契数列。

def fib_generator(n):
    a, b = 0, 1
    for i in range(n):
        yield a
        a, b = b, a+b

使用生成器实现斐波那契数列可以得到一个无限长度的迭代器，避免了存储整个数列，是一种非常节省内存的方法。

4. 矩阵法

矩阵法是一种更加高效的斐波那契数列求解方法，通过矩阵运算可以一次计算出多个数值。

def fib_matrix(n):
    if n < 2:
        return n
    F = [[1, 1], [1, 0]]
    res = matrix_power(F, n-1)
    return res[0][0]

def matrix_power(F, n):
    if n == 1:
        return F
    else:
        H = matrix_power(F, n//2)
        if n % 2 == 0:
            return matrix_mult(H, H)
        else:
            return matrix_mult(matrix_mult(H, H), F)

def matrix_mult(F, G):
    a = F[0][0] * G[0][0] + F[0][1] * G[1][0]
    b = F[0][0] * G[0][1] + F[0][1] * G[1][1]
    c = F[1][0] * G[0][0] + F[1][1] * G[1][0]
    d = F[1][0] * G[0][1] + F[1][1] * G[1][1]
    return [[a, b], [c, d]]

矩阵法的时间复杂度是恒定的（O(log n)），是时间效率最高的方法之一。

示例说明

示例一

假设要计算斐波那契数列的第 6 个数。

使用递推法：

fib_iterative(6)

输出：8

示例二

假设要生成斐波那契数列的前 10 个数。

使用生成器：

for num in fib_generator(10):
    print(num, end=" ")

输出：0 1 1 2 3 5 8 13 21 34