Итерационной версию этой рекурсивной функции

Question

У меня есть функция, которая определяется таким образом:

F(n) = nif n<=3

F(n) = F(n-1) + 2 * F(n-2) + 3 * F(n-3)if n>3

Теперь, я написал это как рекурсивная функция, и она отлично работает. Я пытаюсь написать его как итеративную функцию, но я не могу заставить ее произойти.

Выход должен быть, например:

print(FRec(5)) =>  22 
print(FRec(10)) => 1657 
print(FRec(15)) => 124905 

Любые советы?

Вот моя рекурсивная реализация:

def FRec(n): 
    if(n <= 3): 
     return n 
    if(n > 3): 
     return FRec(n - 1) + 2 * FRec(n - 2) + 3 * FRec(n - 3) 

Answer 1

Все, что вам нужно держать последние 3 результаты:

from collections import deque 

def F_iter(n): 
    if n <= 3: 
     return n 
    prev = deque([1, 2, 3], maxlen=3) 
    for i in range(4, n + 1): 
     result = prev[-1] + 2 * prev[-2] + 3 * prev[-3] 
     prev.append(result) 
    return prev[-1] 

Если deque не «доступен» для вас, то вы можете нерационально заменить что с некоторым списком нарезки и конкатенации:

prev = [1, 2, 3] 
    for i in range(4, n + 1): 
     result = prev[-1] + 2 * prev[-2] + 3 * prev[-3] 
     prev = prev[1:] + [result] 

Демонстрация:

>>> F_iter(5) 
22 
>>> F_iter(10) 
1657 
>>> F_iter(15) 
124905