用 Python 实现斐波那契数列：5 种方法全解析（附性能对比与实战建议）

🔧标签：Python 算法 数据结构 递归 动态规划 生成器 性能优化

🎯 引言：为什么斐波那契是编程“入门必修课”？

斐波那契数列（Fibonacci Sequence）是一个经典的数学序列：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
定义为：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

它不仅是数学之美，更是编程思维的试金石。
掌握它的多种实现方式，意味着你真正理解了：

• 循环与递归
• 时间复杂度与空间复杂度
• 记忆化与动态规划
• 生成器与内存优化

✅ 方法一：【最优】循环迭代法（推荐级）

这是最实用、最高效的写法，也是你写的版本！

def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a

🔍 优点：

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 代码简洁，逻辑清晰
• 支持大数计算（如 fib_iter(10000) 不会爆栈）

💡 使用建议：

• 日常使用首选！
• 适用于绝大多数场景，尤其是 n 较大时

✅ 方法二：【不推荐】朴素递归法（反面教材）

def fib_recursive(n):
if n <= 1:
return n
return fib_recursive(n – 1) + fib_recursive(n – 2)

🔍 问题：

• 时间复杂度：O(2^n) —— 指数级增长，效率极低
• 空间复杂度：O(n) —— 递归深度
• 存在大量重复计算（如 fib_recursive(5) 会重复计算 fib_recursive(3) 两次）

💡 结果：

• n > 30 就明显卡顿
• 仅用于理解递归思想，不要在生产环境使用

✅ 方法三：【推荐】记忆化递归（动态规划思想）

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n – 1) + fib_memo(n – 2)

🔍 优点：

• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 利用缓存避免重复计算
• 代码接近数学定义，可读性强

💡 适用场景：

• 学习“记忆化”、“动态规划”的绝佳案例
• 适合中等规模数据（如 n < 10⁵）

✅ 方法四：【推荐】生成器版本（内存友好）

def fib_generator(n):
a, b = 0, 1
count = 0
while count < n:
yield a
a, b = b, a + b
count += 1

# 使用方式
for num in fib_generator(10):
print(num, end=' ')
# 输出：0 1 1 2 3 5 8 13 21 34

🔍 优点：

• 不一次性生成所有数，节省内存
• 支持 next() 逐个获取
• 适合处理大数据或无限序列

💡 适用场景：

• 处理大量数据（如前 100 万个斐波那契数）
• 流式处理、实时输出

✅ 方法五：【高级】矩阵快速幂（超快！）

适用于：求第百万个斐波那契数 的极致性能需求。

def matrix_multiply(A, B):
return [
[A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
[A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
]

def matrix_power(mat, n):
if n == 1:
return mat
if n % 2 == 0:
half = matrix_power(mat, n // 2)
return matrix_multiply(half, half)
else:
return matrix_multiply(mat, matrix_power(mat, n – 1))

def fib_fast(n):
if n <= 1:
return n
base_matrix = [[1, 1], [1, 0]]
result_matrix = matrix_power(base_matrix, n)
return result_matrix[0][1]

🔍 优点：

• 时间复杂度：O(log n)
• 极速计算，适合超大数

💡 适用场景：

• 求第 10⁶ 个斐波那契数
• 算法竞赛、高性能计算

📊 性能对比总结表

🎯 最佳实践建议

• 日常开发 → 用循环迭代法（你写的那个）
• 学习算法 → 用记忆化递归
• 处理大数据 → 用生成器
• 追求极致性能 → 用矩阵快速幂

🛠️ 扩展练习题（挑战一下）

📎 附录：一键运行脚本模板

"""
【推荐】斐波那契函数合集（可直接复制使用）
"""
from functools import lru_cache

# 1. 循环迭代（最优）
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a

# 2. 记忆化递归（推荐学习）
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n – 1) + fib_memo(n – 2)

# 3. 生成器（内存友好）
def fib_gen(n):
a, b = 0, 1
for _ in range(n):
yield a
a, b = b, a + b

# 测试
if __name__ == "__main__":
print("前10个斐波那契数：")
print(list(fib_gen(10)))