Растет ли стек 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).