python 中 `@lru_cache` 的底层 c 实现会额外占用 c 栈空间，导致即使 python 层递归深度相同，c 层栈也极易溢出；而纯 python 递归在 3.11+ 已通过内联调用优化避免了 c 栈消耗，因此更耐深递归。
在解决树形动态规划（如 CSES 1674：统计每个员工的下属人数）时，你可能会自然写出递归 DFS，并尝试用 @lru_cache 加速。但令人困惑的是：*完全相同的树结构、相同的递归逻辑、甚至相同的 `sys.setrecursionlimit(2 109)设置，加了@lru_cache就崩溃（0xC00000FD`），不加却能稳定运行百万级节点——这并非算法问题，而是 Python 运行时底层机制的差异所致。
? 根本原因：C 栈 vs Python 栈
functools.lru_cache 在 CPython 3.11 及更早版本中是 纯 C 实现（见 _functoolsmodule.c），每次被装饰函数调用时，都会触发一次 C 函数调用链（_lru_cache_wrapper → 原函数）。这意味着：
✅ 每次递归不仅压入 Python 栈帧，还压入一个 C 栈帧；
❌ C 栈默认大小极小（Windows/Linux 通常仅 1–8 MB），对应安全递归深度仅数千到数万；
⚠️ 即使你用 sys.setrecursionlimit(2e9) 抬高 Python 限制，CPython 3.11 仍会盲目尝试执行超深 C 递归，最终 C 栈溢出，进程被操作系统强制终止（退出码 0xC00000FD）。-
而纯 Python 递归（无装饰器）在 Python 3.11+ 中已启用 Inlined Python Function Calls（PEP 659 优化）：当 Python 函数直接调用另一个 Python 函数时，解释器可跳过 C 层调度，复用当前 C 栈帧，仅增长 Python 栈。因此：
- sys.setrecursionlimit() 对其生效；
- 实际 C 栈深度几乎恒定（≈1），真正受限的是 Python 栈（可通过 setrecursionlimit 扩展）；
- 故 200,000 层递归轻松通过，甚至测试 20,000,000 层也不会崩溃（只会抛 RecursionError）。
? 验证：Python 3.12 的行为变化
Python 3.12 明确分离了限制机制（What’s New）：
“The recursion limit now applies only to Python code. Built-in functions do not use the recursion limit, but are protected by a different mechanism…”
这意味着：
- @lru_cache 的 C 递归不再受 setrecursionlimit 影响，而由独立的 C 栈保护机制拦截（在浅层即报 RecursionError）；
- 你的原始带缓存代码在 3.12 中将抛出清晰的 RecursionError（而非静默崩溃），但依然失败——因为 C 层递归深度上限仍只有几千。
✅ 解决方案：绕过 C 层，用纯 Python 缓存
若必须使用缓存且需超深递归，应避免 C 实现的 lru_cache。以下是一个轻量、等效的纯 Python 替代实现：
def lru_cache(_):
def decorator(func):
memo = {}
def wrapper(x):
if x not in memo:
memo[x] = func(x)
return memo[x]
return wrapper
return decorator
# 使用方式完全一致
@lru_cache(None)
def dfs(v: int) -> int:
if not graph[v]:
return 0
return sum(dfs(u) + 1 for u in graph[v])✅ 此版本全程运行在 Python 层，享受 3.11+ 的内联优化，与手动 DP 版本具有同等栈鲁棒性。
⚠️ 注意事项与最佳实践
- 不要滥用 sys.setrecursionlimit：它无法突破操作系统 C 栈硬限，盲目调高反而掩盖问题；
- 深递归优先考虑迭代化：对树 DFS，可用显式栈（list）或 BFS 层序遍历，彻底规避递归；
- 缓存选型需谨慎：@cache / @lru_cache 适合「浅层+高重复调用」场景；对「单次深遍历+无重叠子问题」（如本题），手动 DP 数组（dp[v]）更高效、更安全；
- 调试技巧：用 import inspect; print(len(inspect.stack())) 监控当前 Python 栈深，辅助定位。
总之，@lru_cache 的崩溃不是你的代码有误，而是 Python 运行时在 C 与 Python 栈之间的一次“越界”。理解这一分界，才能在性能与稳定性间做出清醒权衡。
