递归栈限制设置

What · 是什么

Python 默认递归深度上限仅 1000（CPython），深递归（如 DFS、树形 DP）会抛 RecursionError。用 sys.setrecursionlimit(N) 可提高上限。但 setrecursionlimit 只是改了 Python 层检查阈值，底层 C 栈若溢出仍会段错误（segfault），尤其在 PyPy 上更常见。终极方案是放线程里设 threading.stack_size 后运行，或改用迭代（手写栈）。

Why · 为什么

How · 实现

伪代码

import sys, threading
sys.setrecursionlimit(1 << 25)
# 方案1: 直接调（可能 segfault 若 C 栈不够）
# main()
# 方案2: 放线程里增大栈
def run(): main()
threading.stack_size(256 << 20)  # 256MB
th = threading.Thread(target=run)
th.start(); th.join()

Python 实现

# 递归栈限制设置（含自测）
import sys
import threading

def deep_sum(n):
    """递归求 1+2+...+n"""
    if n == 0:
        return 0
    return n + deep_sum(n - 1)

def run_with_big_stack(func, *args, stack_mb=256):
    """在大栈线程中运行 func，避免 C 栈溢出 segfault"""
    result = [None]
    def wrapper():
        result[0] = func(*args)
    threading.stack_size(stack_mb * (1 << 20))
    th = threading.Thread(target=wrapper)
    th.start()
    th.join()
    return result[0]

if __name__ == "__main__":
    # 默认限制 1000，递归 1001 层应抛 RecursionError
    try:
        deep_sum(2000)
        raised = False
    except RecursionError:
        raised = True
    assert raised, "默认限制应拦截深递归"

    # 放宽限制
    sys.setrecursionlimit(1 << 20)
    assert deep_sum(100000) == 100000 * 100001 // 2

    # 更深递归放线程大栈运行
    sys.setrecursionlimit(1 << 25)
    val = run_with_big_stack(deep_sum, 500000, stack_mb=512)
    assert val == 500000 * 500001 // 2
    print("py-recursion-limit OK")

易错点

• 只设 setrecursionlimit 不增大 C 栈 → segfault（尤其在 PyPy）
• 设了 limit 但线程栈不够大，仍 segfault；须二者配合
• 交互题用线程方案可能导致输出缓冲乱序，需在 join 后统一输出
• PyPy 下深递归即使不崩溃也极慢，应优先改写成迭代（手写栈）
• 忘了 setrecursionlimit 导致正常大小的树 DFS 在 Python 抛 RecursionError

例题

信源

• OI Wiki✓ https://oi-wiki.org/lang/python/
• web✓ https://docs.python.org/3/library/sys.html#sys.setrecursionlimit
• web✓ https://docs.python.org/3/library/threading.html#threading.stack_size