将递归算法转换为迭代算法

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))