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