python - リストを使用してPythonで再帰用のスタックを合成しますか？例？

Question

たとえば、これは私の階乗関数です。

def fact(n):
    if n<=1: return 1
    else: return n*fact(n-1)

ただし、nが高すぎるとクラッシュします。スタックエミュレーションを使用して、これとまったく同じ関数をエミュレートしたいと思います。どうすればこのようなことができますか？末尾再帰でない場合はどうなりますか？説明を見つけるのに苦労しています。

Answer 1

まず、末尾再帰にすることができます。

def tfact(n,acc=1):
    if n<=1: return acc
    else: return tfact(n-1,acc*n)

しかし、より直接的な翻訳の場合：

def ifact(n):
    stack = []
    while True:
        if n==1:
            while stack:
                n *= stack.pop()
            break
        else:
            stack.append(n)
            n -= 1
    return n