不导入sys如何解决递归深度超出问题？递归代码报错求助

问题根源 #

你的代码遇到的maximum recursion depth exceeded问题，本质是重复递归调用次数过多，导致Python调用栈被撑爆。即使调高递归限制到2000也没用，因为这类测试用例的递归分支会指数级增长。另外原代码没处理n>0且m=0的边界情况——这种场景下应该返回0，毕竟没法把正数分成0组。

两种可行的修复方案 #

方案1：用动态规划替代递归（推荐） #

动态规划通过迭代填充表格的方式，完全避开递归栈的问题，同时时间复杂度更低：

def howManyGroups(n, m):
    if n == 0:
        return 1
    if m == 0:
        return 0
    m = min(m, n)
    # dp[i][j] 表示把i个元素分成最多j组的方式数
    dp = [[0]*(m+1) for _ in range(n+1)]
    
    # 初始化边界：0个元素分任意组都只有1种方式；任意元素分1组也只有1种方式
    for j in range(m+1):
        dp[0][j] = 1
    for i in range(n+1):
        dp[i][1] = 1
    
    # 填充dp表
    for i in range(1, n+1):
        for j in range(2, m+1):
            if i >= j:
                dp[i][j] = dp[i][j-1] + dp[i-j][j]
            else:
                dp[i][j] = dp[i][j-1]
    return dp[n][m]

方案2：优化递归+记忆化缓存 #

如果想保留递归写法，可以用记忆化缓存把已经计算过的结果存起来，避免重复递归，同时修正边界条件：

import sys
sys.setrecursionlimit(2000)
from functools import lru_cache

@lru_cache(maxsize=None)
def howManyGroups(n, m):
    # 修正m=0的边界逻辑
    if m == 0:
        return 0 if n > 0 else 1
    m = min(m, n)
    if n == 0 or m == 1:
        return 1
    return howManyGroups(n, m - 1) + howManyGroups(n - m, m)

关键说明 #

• 原代码的最大问题是每次递归都会触发两个新的递归调用，且大量计算是重复的，导致栈深度急剧上升
• 动态规划从底往上计算，彻底消除递归栈溢出风险
• 记忆化缓存通过缓存已计算的(n,m)结果，把递归的时间复杂度从指数级降到线性级，栈深度也会大幅降低

内容的提问来源于stack exchange，提问作者Ian Dang