递归一万层报 StackOverflowError 改迭代要注意什么

目录树导出脚本递归遍历,测试数据 1.2 万层,Python 3.11 直接抛 ReCursionError: maximum recursion depth exceeded,默认上限 1000。第一反应是 sys.setrecursionlimit(20000),结果进程收到 SIGSEGV,core dumped,比异常还难看。

原因是 Python 的调用栈和 C 栈绑在一起。解释器层数放开了,C 层每个 eval 帧还在吃栈,8MB 的线程栈撑不到两万层。所以调大 limit 只是把报错换成崩溃,线上更不能这么干。

改迭代。DFS 用显式栈,节点和深度一起压栈。要保证和递归一样的访问顺序,子节点得逆序入栈。这一步最容易写错,我第一版忘了 reversed,导出的目录顺序整个反了,比对文件时才发现。

def walk(root):
    stack = [(root, 0)]
    while stack:
        node, depth = stack.pop()
        if depth >= 10000:
            continue
        for ch in reversed(node.children):
            stack.append((ch, depth + 1))

还有一个变化:递归时每层的局部变量在栈帧里自动释放,改成循环以后如果拿列表存了所有节点,内存会涨。我们的树 1.2 万层、40 万个节点,一开始把 path 列表整个拷进栈,内存冲到 2.3G;改成只存父指针、需要时回溯,降到 180MB。

树特别深时还要注意,迭代版的深度由数据决定,不再有保护。加一个最大深度参数,超过就记日志跳过,避免脏数据把内存拖死。我们那批数据里确实有一条自己指向自己的脏节点,递归版直接崩,迭代版会死循环,这个防护是必须的。

改完同样数据跑了 4.7 秒,递归版在 800 层时是 3.9 秒,慢了一点,但不会再崩。尾部递归那种场景其实用 while 就够了,不用显式栈,代码还能更短。

您可以还会对下面的文章感兴趣: