Я прочитал довольно много материала по теме c рекурсии. И часто упоминается, что из-за роста стека вызовов рекурсивный обычно считается «более медленным» по сравнению с реализацией al oop. Но я не могу найти достаточно четкого объяснения того, как именно сравнить использование памяти в обоих сценариях ios.
Насколько я понимаю, это посредством реализации факториальной функции:
# python
# loop imp
def factorial_f(n):
fac = 1
for i in range(1, n + 1):
fac = fac * i
return fac
Таким образом, сложность пространства здесь составляет 1 слот для n, 1 слот для i, 1 слот для fa c, поэтому O (3) = O (1)?
# python
# recursion imp
def factorial_r(n):
if n == 1:
return n
return n*factorial_r(n-1)
Пространственная сложность - это n слотов (n слотов стека вызовов) для n, поэтому O (n)?
Поэтому мы получаем вывод, что l oop лучше с точки зрения эффективности?
Я не на 100%, если этот образ мышления верен. Пожалуйста, порекомендуйте. Спасибо!