"""
斐波那契数列
"""
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
print(fib(10))下面为你详细解释这段Python代码的含义、实现原理、用途以及注意事项。
### 1. 代码含义
这段代码的主要功能是**计算并输出斐波那契数列的第10项的值**。
斐波那契数列是一个经典的数学序列，其规则是：从第2项开始，每一项的值都等于前两项的值之和。数列的前几项为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
代码最终输出的 fib(10) 的结果为 55。
### 2. 实现原理
这段代码使用了**递归**的方式来实现了斐波那契数列的计算：
* 基线条件（Base Case）：递归的终止条件。代码中规定，当 n 0 时返回 0，当 n 1 时返回 1。这对应了斐波那契数列的前两项。
* 递归条件：将问题分解为更小的子问题。对于 n >= 2 的情况，函数通过调用自身 fib(n-1) + fib(n-2) 来计算结果，这完美契合了斐波那契数列的数学定义 $F(n) = F(n-1) + F(n-2)$。
当执行 fib(10) 时，函数会不断向下拆解，直到触碰到 fib(0) 或 fib(1)，然后再将结果层层向上相加返回。
### 3. 用途
* 算法教学：这是计算机科学中讲解“递归”概念最经典的入门案例之一。
* 数学与金融模型：斐波那契数列在自然界（如花瓣数量、海螺螺旋）、数学（黄金分割）以及金融分析（斐波那契回调线）中都有广泛应用。
* 动态规划入门：它常被用来引出“重叠子问题”的概念，是学习动态规划和记忆化搜索的最佳切入点。
### 4. 注意事项（⚠️重要）
虽然这段递归代码非常简洁易懂，但在实际工程中**极其不推荐**使用这种方式来计算斐波那契数列，原因如下：
* 严重的性能问题（指数级时间复杂度）：该算法的时间复杂度为 $O(2^n)$。因为它存在大量的**重复计算**。例如计算 fib(5) 时fib(3) 会被计算1次；但在计算 fib(10) 时fib(3) 会被重复计算几十次。当 n 稍大（如 n=40）时，程序运行会非常缓慢n=50 时甚至可能卡死。
* 栈溢出风险：Python 默认的递归深度限制通常是 1000。如果传入的 n 超过这个限制（如 fib(2000)），程序会抛出 RecursionError: maximum recursion depth exceeded 错误。
### 5. 改进建议
为了解决上述问题，在实际开发中通常采用以下优化方式：
方法一：迭代法（推荐，时间复杂度 $O(n)$，空间复杂度 $O(1)$）
```python
def fib_iterative(n):
if n == 0: return 0
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fib_iterative(10)) # 输出 55
```
方法二：带缓存的递归/记忆化搜索（时间复杂度 $O(n)$，空间复杂度 $O(n)$）
使用 functools.lru_cache 自动缓存计算结果，避免重复计算：
```python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n == 0: return 0
elif n == 1: return 1
return fib_memo(n-1) + fib_memo(n-2)
print(fib_memo(10)) # 输出 55
```
总结：这段代码是学习递归的优秀示例，但出于性能考虑，不应在生产环境中用于计算较大数值的斐波那契数列。