python 中 `@lru_cache` 的底层 c 实现会额外消耗 c 栈空间，导致即使设置极高 `recursionlimit` 仍触发系统级栈溢出；而纯 python 递归（如手动 dp）在 python 3.11+ 已通过内联调用优化，几乎不占用 c 栈，因此能安全处理数十万层递归。
在解决树形动态规划问题（例如 CSES “Subordinates”）时，你可能会自然地写出带记忆化的递归 DFS，并尝试用 @lru_cache(None) 加速。但当树退化为一条链（即最坏情况：200,000 层深度），程序却意外崩溃：
Process finished with exit code -1073741571 (0xC00000FD)
这是 Windows 下典型的 C 栈溢出（stack overflow） 错误 —— 并非 Python 的 RecursionError，而是操作系统强制终止进程。关键原因在于：@lru_cache 是用 C 实现的（见 CPython 源码），每次缓存命中或未命中都会引入一层 C 函数调用帧。你的 dfs(v) 调用 → lru_cache_wrapper → dfs(v) 的递归链，实际是 Python + C 混合递归，C 栈深度随递归线性增长。
相比之下，手动 DP 版本：
dp = [0] * n
def dfs(v):
for u in graph[v]:
dfs(u)
dp[v] += dp[u] + 1仅涉及纯 Python 函数调用。自 Python 3.11 起，解释器引入了 内联 Python 调用（inlined Python function calls） 优化：当一个 Python 函数直接调用另一个 Python 函数时，不再经过 C 层的通用调用机制（_PyEval_EvalFrameDefault），从而几乎不消耗 C 栈空间。这意味着：即使递归 200,000 层，C 栈深度可能仅维持在个位数，完全避开系统栈限制。
✅ 验证：将 n = 2_000_000（10 倍规模）传入手动 DP 版本，在主流环境下仍稳定运行；而 @lru_cache 版本在 n > ~10_000 时就极可能崩溃（取决于系统默认 C 栈大小，通常仅 1–8 MB，对应数千至数万 C 帧）。
Python 3.12 的行为变化
Python 3.12 进一步明确了这一边界：sys.setrecursionlimit() 仅约束 Python 字节码层面的递归深度，不再影响 C 扩展的递归。因此：
- @lru_cache 版本在 3.12 中会抛出清晰的 RecursionError（而非崩溃），因为 C 层递归被内部机制主动截断；
- 手动 DP 版本依然畅通无阻，得益于内联优化。
解决方案与最佳实践
✅ 推荐：避免在超深递归中使用 @lru_cache
对树形 DP 等可能深度递归的场景，优先采用显式状态数组（如 dp[]）或迭代 DFS/BFS：
# 迭代版（拓扑序 + 自底向上）
from collections import deque
order = []
stack = [0]
while stack:
v = stack.pop()
order.append(v)
for u in graph[v]:
stack.append(u)
# 反向更新 dp
dp = [0] * n
for v in reversed(order):
for u in graph[v]:
dp[v] += dp[u] + 1⚠️ 替代方案（仅用于学习/调试）
若坚持用记忆化，可替换为纯 Python 实现的简易缓存（无 C 开销）：
def simple_cache(_):
def decorator(func):
memo = {}
def wrapper(x):
if x not in memo:
memo[x] = func(x)
return memo[x]
return wrapper
return decorator
@simple_cache(None)
def dfs(v):
# ... same logic? 注意：此实现不支持多参数、kwargs 或复杂键类型，仅作原理演示。生产环境请优先用显式 DP 或迭代。
? 不推荐的“黑科技”
虽然可通过 del _functools._lru_cache_wrapper 强制回退到 Python 版 lru_cache，或修改标准库源码，但这类 hack 破坏可移植性与可维护性，且可能引发兼容性问题，应严格避免。
总结
| 方案 | 递归类型 | C 栈消耗 | Python 3.11 行为 | Python 3.12 行为 |
|---|---|---|---|---|
| @lru_cache | Python + C 混合 | 高（线性增长） | 系统级栈溢出（崩溃） | RecursionError（受保护） |
| 手动 dp[] | 纯 Python | 极低（内联优化） | 稳定运行 | 稳定运行 |
| 迭代 DP | 无递归 | 零 | 最安全 | 最安全 |
根本原则：对可预见的超深递归（>10⁴ 层），放弃装饰器记忆化，拥抱显式状态管理或迭代算法。 这不仅是 Python 的工程实践，更是理解解释器底层行为的关键一课。
