用 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,) # 输出：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⁶ 个斐波那契数
- 算法竞赛、高性能计算
📊 性能对比总结表
| 方法 | 时间复杂度 | 空间复杂度 | 是否推荐 | 适用场景 |
|---|---|---|---|---|
| 循环迭代 | O(n) | O(1) | ✅✅✅ 强烈推荐 | 大多数情况 |
| 朴素递归 | O(2ⁿ) | O(n) | ❌ 不推荐 | 教学演示 |
| 记忆化递归 | O(n) | O(n) | ✅ 推荐 | 学习动态规划 |
| 生成器 | O(n) | O(1) | ✅ 推荐 | 大数据/流式处理 |
| 矩阵快速幂 | O(log n) | O(log n) | ✅ 高级使用 | 超大数计算 |
🎯 最佳实践建议
- 日常开发 → 用循环迭代法（你写的那个）
- 学习算法 → 用记忆化递归
- 处理大数据 → 用生成器
- 追求极致性能 → 用矩阵快速幂
🛠️ 扩展练习题（挑战一下）
- 写一个函数，返回前 n 个斐波那契数的列表（用生成器）
- 写一个函数，判断某个数是否为斐波那契数
- 画出斐波那契数列的图形（用 matplotlib）
- 模拟“兔子繁殖”问题（经典故事背景）
📎 附录：一键运行脚本模板
""" 【推荐】斐波那契函数合集（可直接复制使用） """ 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)))
