python - python 堆栈是否随着递归过程执行的迭代过程而增长？

Question

我知道 Python 不支持尾调用优化。这是否意味着具有迭代过程的递归过程（如我在下面定义的阶乘）会消耗 O(n) 内存，或者没有延迟操作这一事实是否意味着空间将为 O(1)？

def factorial(n, accum=1):
    if n == 0:
        return accum
    else:
        return factorial(n-1, accum * n)

score 5 · Accepted Answer

内存将是 O(n)。如果 python 优化了这种情况，那么在递归深处发生的异常不会有完整的堆栈跟踪。您可以通过让基本案例引发异常来自己测试它是否如此，您将看到完整的堆栈跟踪。

score 2 · Accepted Answer

没有尾调用优化意味着您需要在递归调用返回之前将堆栈保留在内存中，因此在我看来，在这种情况下内存使用量将是 O(n)。

如果您想自己检查它，只需运行您的示例代码以获得较大的值n（使用sys.setrecursionlimit）并检查内存使用情况top应该让您相信这不是 O(1)。

2 回答 2