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）。