转换递归算法，以迭代

Question

我已经做在Python递归函数的工作原理：

def Rec(n): 
    if (n<=5): 
     return 2*n 
    elif (n>=6): 
     return Rec(n-6)+2*Rec(n-4)+4*Rec(n-2) 
print (Rec(50)) 

但我想不出一个迭代
我相信我会需要使用一个循环，并可能有4个变量来存储
以前的值，模仿一个堆栈。

Answer 1

对于你的特定问题，假设你有一个输入n，下面的代码应该在python中迭代计算函数。

val = [] 
for i in range(6): 
    val.append(2*i) 

for i in range(6,n+1): 
    val.append(val[i-6] + 2*val[i-4] + 4*val[i-2]) 

print(val[n]) 

Answer 2

我得到这样的回答：

$ python test.py 
Rec(50) = 9142785252232708 
Kist(50) = 9142785252232708 

使用下面的代码。这个想法是，你的函数需要一个以前值的“窗口” - Kn-6，Kn-4，Kn-2 - 并且当你计算新值时，该窗口可以“滑动”。

因此，对于像“14”这样的一些值，您将有一个K8，K9，... K13的窗口。只需使用这些值进行计算，然后放弃K8，因为您将永远不会再使用它，并附加K14，以便在计算K15..20时使用它。

def Rec(n): 
    if (n<=5): 
     return 2*n 
    elif (n>=6): 
     return Rec(n-6)+2*Rec(n-4)+4*Rec(n-2) 

def Kist(n): 
    if n <= 5: 
     return 2 * n 

    KN = [2*n for n in range(6)] 
    for i in range(6, n+1): 
     kn = KN[-6] + 2 * KN[-4] + 4 * KN[-2] 
     KN.append(kn) 
     KN = KN[-6:] 

    return KN[-1] 


print("Rec(50) =", Rec(50)) 
print("Kist(50) =", Kist(50))