斐波那契数列

在 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) 因为需要存储每一步的结果。

选择最佳实现

• 递归：简洁但效率低。
• 记忆化递归：解决了递归的效率问题。
• 迭代：最优的时间和空间复杂度。
• 动态规划（数组）：适合需要保存所有中间结果的场景。

大多数情况下，迭代版本 是面试中推荐的最佳解法，因为它时间和空间效率都很好。