Python 3背包递归代码报错求助，疑非递归深度超限问题

你的递归深度超限确实是代码逻辑错误导致的，核心问题出在递归分支里的变量误用：

错误点分析 #

在knapSack函数的else分支中，你错误地使用了全局变量n来索引和传递递归参数，而不是用函数参数i。每次递归调用时，你传入的都是n-1（固定为10），导致递归永远无法触碰到i == 0的终止条件，最终触发递归深度超限错误。

同时，取当前物品的价值和重量时，用pi[n-1]和wi[n-1]也不对，应该对应当前递归层级的i-1。

修复后的代码 #

def knapSack(W, wi, pi, i):
    
    if i == 0 or W == 0:
        return 0

    if wi[i-1] > W:
        return knapSack(W, wi, pi, i-1)

    else:
        return max(
            pi[i-1] + knapSack(W - wi[i-1], wi, pi, i-1),
            knapSack(W, wi, pi, i-1))

pi = [25, 5, 20, 120, 100, 0, 30, 0, 0, 75, 100]
wi = [2, 4, 1, 8, 10, 5, 3, 7, 6, 12, 7]
W = 30
n = len(pi)
print(knapSack(W, wi, pi, n))

补充说明 #

递归版01背包的时间复杂度是O(2^n)，当物品数量n较大时（比如超过20），不仅运行速度会极慢，还有可能再次触发递归深度问题。后续可以考虑添加记忆化缓存（比如用lru_cache装饰器），或者改用动态规划的迭代版本来优化性能。

内容的提问来源于stack exchange，提问作者Sina sam sina_mix