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