python中的递归函数为什么会出现Memory Error？

Question

我在 python 中使用递归编写了一段代码来获取字符串的所有子序列。下面是代码。

def solve(s):

    if (len(s)==0):
        return [""]
    curr = s[0]
    res = s[1:]
    ans = solve(res)
    for i in ans:
        ans.append(curr+i)
    return ans
if __name__=="__main__":
    s=str(input())
    print(solve(s))

对于输入 = "ab"，上面的代码抛出 内存错误

我不确定为什么会这样。

将代码更改为以下代码后，它起作用了。

def solve(s):

    if (len(s)==0):
        return [""]
    curr = s[0]
    res = s[1:]
    ans = solve(res)
    new = []
    for i in ans:
        new.append(i)
        new.append(curr+i)

    return new

if __name__=="__main__":
    s=str(input())
    print(solve(s))

谁能解释一下第一个代码中 Memory Error 背后的原因是什么？提前致谢。

Answer 1

这个：

for i in ans:
    ans.append(curr+i)

您正在迭代 ans 并同时在 ans 的末尾添加内容。这是一个无限循环：你永远不会到达 ans 的结尾，因为你不断地让它变长（直到你运行内存不足）。

如果您想向 ans 添加新元素，即每个现有元素前面都有 curr，您可以通过列表理解来实现：

ans += [curr + i for i in ans]

这种方式计算所有新元素，然后然后将它们全部添加到ans，而不是扩展ans。

python中的递归函数为什么会出现Memory Error？

Why is there Memory Error in recursion function in python?

python

recursion

memory

memory-management

subsequence