在 Python 3.11 中实现斐波那契数列的常见方式有多种，下面我将展示几种不同的实现方法，包括递归、迭代和使用缓存（动态规划）来优化递归版本。
1. 递归方式（最简单但效率较低）
def fibonacci_recursive(n):if n <= 1:return nreturn fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)# 测试
print(fibonacci_recursive(10)) # 输出 55
这种方式的时间复杂度是 O(2^n)，因为每次调用都会递归两次，对于较大的 n，效率较低。
2. 使用缓存优化递归（动态规划 + 记忆化）
使用 Python 的 functools.lru_cache 装饰器，可以将之前计算的结果缓存，避免重复计算。
from functools import lru_cache@lru_cache(maxsize=None)
def fibonacci_memoization(n):if n <= 1:return nreturn fibonacci_memoization(n - 1) + fibonacci_memoization(n - 2)# 测试
print(fibonacci_memoization(10)) # 输出 55
这个版本的时间复杂度是 O(n)，空间复杂度也是 O(n)，因为每个斐波那契数只会计算一次。
3. 迭代方式（最有效率）
迭代方式可以在 O(n) 的时间内完成，并且只需要常量级的空间 O(1)。
def fibonacci_iterative(n):if n <= 1:return na, b = 0, 1for _ in range(2, n + 1):a, b = b, a + breturn b# 测试
print(fibonacci_iterative(10)) # 输出 55
4. 动态规划方式（使用数组）
这种方式通过数组存储中间结果，也是一种动态规划的实现。
def fibonacci_dp(n):if n <= 1:return ndp = [0] * (n + 1)dp[1] = 1for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]# 测试
print(fibonacci_dp(10)) # 输出 55
这个版本的时间复杂度是 O(n)，但空间复杂度是 O(n) 因为需要存储每一步的结果。
选择最佳实现
- 递归：简洁但效率低。
- 记忆化递归：解决了递归的效率问题。
- 迭代：最优的时间和空间复杂度。
- 动态规划（数组）：适合需要保存所有中间结果的场景。
大多数情况下，迭代版本 是面试中推荐的最佳解法，因为它时间和空间效率都很好。