python 斐波那契数列递归实现

在 Python 中，斐波那契数列的递归实现是经典的递归示例。斐波那契数列的定义为： - \( F(0) = 0 \) - \( F(1) = 1 \) - \( F(n) = F(n-1) + F(n-2) \) （当 \( n \geq 2 \)） ### **1. 基础递归实现** ```python def fibonacci(n): if n <= 1: # 基线条件：F(0)=0, F(1)=1 return n else: return fibonacci(n - 1) + fibonacci(n - 2) # 递归调用 # 示例 print(fibonacci(5)) # 输出: 5 (0, 1, 1, 2, 3, 5) ``` #### **问题**：效率低下（时间复杂度 \( O(2^n) \)） 每次计算 \( F(n) \) 会重复计算 \( F(n-1) \) 和 \( F(n-2) \)，导致指数级增长。 --- ### **2. 优化方法** #### **(1) 记忆化（Memoization）** 使用缓存存储已计算的结果，避免重复计算： ```python from functools import lru_cache @lru_cache(maxsize=None) # 无限缓存 def fibonacci_memo(n): if n <= 1: return n return fibonacci_memo(n - 1) + fibonacci_memo(n - 2) print(fibonacci_memo(50)) # 快速输出 ``` **优点**：时间复杂度降至 \( O(n) \)，空间复杂度 \( O(n) \)。 #### **(2) 迭代法（非递归）** ```python def fibonacci_iter(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return a print(fibonacci_iter(50)) # 高效计算 ``` **优点**：时间 \( O(n) \)，空间 \( O(1) \)，无递归栈开销。 --- ### **3. 递归与迭代的对比** | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | |---------------|------------|------------|-----------------------| | 基础递归 | \( O(2^n) \) | \( O(n) \) | 教学演示（不推荐实际使用） | | 记忆化递归 | \( O(n) \) | \( O(n) \) | 需要递归逻辑且 \( n \) 较小 | | 迭代法 | \( O(n) \) | \( O(1) \) | 推荐实际使用 | --- ### **4. 尾递归优化（Python 不支持，但可模拟）** Python 默认不支持尾递归优化（TCO），但可通过参数传递模拟： ```python def fibonacci_tail(n, a=0, b=1): if n == 0: return a return fibonacci_tail(n - 1, b, a + b) print(fibonacci_tail(50)) # 仍可能栈溢出（Python 无 TCO） ``` --- ### **5. 注意事项** 1. **递归深度限制**：Python 默认递归深度约 1000，计算 \( F(1000) \) 会触发 `RecursionError`。 **解决方法**：改用迭代或增加限制（`sys.setrecursionlimit(2000)`，但不推荐）。 2. **性能权衡**：递归代码简洁但效率低，迭代更高效但可能牺牲可读性。 --- ### **完整代码示例** ```python # 基础递归（不推荐） def fib_recursive(n): return n if n <= 1 else fib_recursive(n - 1) + fib_recursive(n - 2) # 记忆化递归（推荐） from functools import lru_cache @lru_cache(maxsize=None) def fib_memo(n): return n if n <= 1 else fib_memo(n - 1) + fib_memo(n - 2) # 迭代法（最佳实践） def fib_iter(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return a # 测试 print(fib_iter(50)) # 输出: 12586269025 ``` --- ### **关键问题总结** 1. **为什么基础递归效率低？** 重复计算子问题（如 \( F(3) \) 被计算多次）。 2. **记忆化如何优化递归？** 通过缓存（如字典或 `lru_cache`）存储中间结果。 3. **Python 递归深度的限制是多少？** 默认约 1000，可通过 `sys.setrecursionlimit()` 调整（但可能引发段错误）。 4. **递归与迭代的斐波那契实现各有什么优缺点？** - 递归：直观但可能栈溢出； - 迭代：高效且无栈限制，但代码稍复杂。 5. **如何计算大规模斐波那契数（如 \( F(10^6) \)）？** 使用矩阵快速幂或通项公式（时间 \( O(\log n) \)）。 --- 递归是理解分治思想的起点，但在实际工程中需结合场景选择最优实现！