lru_cache 与动态编程、stackoverflow 有一个但另一个没有？

Question

我正在树上做这个基本的 dp（动态规划）问题（https://cses.fi/problemset/task/1674/）。给定公司的结构（层次结构是一棵树），任务是计算每个员工的下属数量。

这个：

import sys
from functools import lru_cache  # noqa
sys.setrecursionlimit(2 * 10 ** 9)

if __name__ == "__main__":
    n: int = 200000
    boss: list[int] = list(range(1, 200001))  
    # so in my example it will be a tree with every parent having one child
    graph: list[list[int]] = [[] for _ in range(n)]

    for i in range(n-1):
        graph[boss[i] - 1].append(i+1)  # directed so neighbours of a node are only its children

    @lru_cache(None)
    def dfs(v: int) -> int:
        if len(graph[v]) == 0:
            return 0
        else:
            s: int = 0
            for u in graph[v]:
                s += dfs(u) + 1
            return s

    dfs(0)

    print(*(dfs(i) for i in range(n)))

崩溃（我用谷歌搜索了错误消息，这意味着堆栈溢出）

Process finished with exit code -1073741571 (0xC00000FD)

然而

import sys
sys.setrecursionlimit(2 * 10 ** 9)

if __name__ == "__main__":
    n: int = 200000
    boss: list[int] = list(range(1, 200001))
    # so in my example it will be a tree with every parent having one child
    graph: list[list[int]] = [[] for _ in range(n)]

    for i in range(n-1):
        graph[boss[i] - 1].append(i+1)  # directed so neighbours of a node are only its children

    dp: list[int] = [0 for _ in range(n)]

    def dfs(v: int) -> None:
        if len(graph[v]) == 0:
            dp[v] = 0
        else:
            for u in graph[v]:
                dfs(u)
                dp[v] += dp[u] + 1

    dfs(0)

    print(*dp)

不是，它的复杂性是完全相同的，对吗？在这两种情况下，dfs 的深度也完全一样吗？我尝试使这两段代码尽可能相似。

我尝试了 20000000 而不是 200000（即图深 100 倍），但第二个选项仍然没有 stackoverflow。显然我可以做一个迭代版本，但我试图理解这两个递归选项之间存在如此大差异的根本原因，以便我可以更多地了解 Python 及其底层功能。

我正在使用

Python 3.11.1

。

Answer 1

lru_cache

是在C中实现的，它的调用与你的函数的调用交错，我认为你的C代码递归太深并且崩溃了。

在 Python 3.11 中，我遇到了类似的严重崩溃：

[Execution complete with exit code -11]

在 Python 3.12 中我刚刚收到一个错误：

Traceback (most recent call last):
  File "/ATO/code", line 34, in <module>
    dfs(0)
  File "/ATO/code", line 31, in dfs
    s += dfs(u) + 1
         ^^^^^^
  File "/ATO/code", line 31, in dfs
    s += dfs(u) + 1
         ^^^^^^
  File "/ATO/code", line 31, in dfs
    s += dfs(u) + 1
         ^^^^^^
  [Previous line repeated 496 more times]
RecursionError: maximum recursion depth exceeded

尽管你的

sys.setrecursionlimit(2 * 10 ** 9)

。

Python 3.12 的新增功能 说：

sys.setrecursionlimit() 和 sys.getrecursionlimit()。递归限制现在仅适用于 Python 代码。内置函数不使用递归限制，而是受到不同机制的保护，以防止递归导致虚拟机崩溃

所以让我们避免 C 递归。如果我使用（简化的）Python 版本的

lru_cache

，该程序在 3.11 和 3.12 中都可以正常工作，无需任何其他更改：

def lru_cache(_):
    def deco(f):
        memo = {}
        def wrap(x):
            if x not in memo:
                memo[x] = f(x)
            return memo[x]
        return wrap
    return deco