Python堆栈是否增长了一个由递归过程执行的迭代过程？

Question

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

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

Answer 1

内存将为O（n）。如果python优化了这种情况，那么发生在递归深处的异常将不会有完整的堆栈跟踪。你可以自己测试它的作用，只是让基本情况引发一个异常，你会看到完整的堆栈跟踪。

Answer 2

无尾调用优化意味着你需要保持堆栈存储器中的递归调用返回前，所以在我看来，内存使用量将是为O（n），在这种情况下。

如果你想自己检查出来，只是运行您的示例代码的n大值（使用的sys.setrecursionlimit），并检查内存使用量top应该说服你，这不是O（1）。