递归实现斐波那契慢因重复计算子问题，时间复杂度达O(2^n)；如fib(5)中fib(3)被调用两次、fib(2)三次，n增大时重复呈指数级增长。
递归实现斐波那契为什么慢到不能用
因为 fib(n) 会重复计算大量子问题，时间复杂度是指数级 O(2^n)。比如算 fib(5) 时，fib(3) 被调用两次，fib(2) 被调用三次——n 越大，重复越恐怖。
实际写出来长这样：
fib(35)
- 没有缓存，纯靠函数调用栈压入弹出，空间复杂度也是
O(n) - Python 默认递归深度限制约 1000，
fib(1000)直接抛RecursionError - 即使加了
@lru_cache，它仍是递归，栈深度和哈希查找开销仍在
用动态规划（自底向上）避免重复计算
核心思路：只保留前两个值，滚动更新。时间复杂度降到 O(n)，空间压缩到 O(1)，且无递归风险。
最简实现：
fib_dp(10**6)
- 每轮只做一次加法和两次赋值，CPU 友好
- 不依赖 Python 的函数调用机制，不受递归限制影响
- 如果需要整个数列，改成
yield或列表追加也只需微调
什么时候该用记忆化递归（@lru_cache）
不是不能用，而是得看场景：适合「查询稀疏、n 不大、逻辑嵌套深」的情况，比如带分支条件的变种斐波那契（如跳台阶限制步数），或者作为教学演示。
加缓存后性能跃升，但仍有边界：
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_cached(n):
if n
-
@lru_cache底层是字典查表，n 极大时内存占用不可忽视（比如缓存 100 万个键值对） - 首次调用仍走递归路径，栈深度仍是瓶颈 ——
fib_cached(2000)还是报RecursionError - 多线程下
@lru_cache非线程安全，高并发需换functools.cache（Py3.9+）或手动加锁
实测性能差距有多夸张
在主流机器上测 n = 35：
-
fib(35)（朴素递归）：约 3.2 秒 -
fib_cached(35)：首次 ~0.0001 秒，后续接近 0 -
fib_dp(35)：稳定 ~0.000008 秒（800 纳秒）
再测 n = 1000：
- 朴素递归：根本跑不完（指数爆炸）
-
fib_cached(1000)：抛RecursionError -
fib_dp(1000)：依然瞬间返回（结果有 209 位数字）
真正上线或处理大 n，别犹豫，直接上迭代版 fib_dp。递归写法只适合理解原理，或极小规模、可预知输入范围的脚本场景。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
