Использование списка для синтеза стека для рекурсии в 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