﻿ Converting recursive algorithm to Iterative - 开发者网 - DeveloperSite.cn

# Converting recursive algorithm to Iterative

Keywords：python

Question:

I have done the Recursive function in Python that works:

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

But I can't think of an iterative one
I am sure I will need to use a loop and possibly have 4 variables to store
the previous values, imitating a stack.

For your particular question, assuming you have an input n, the following code should calculate the function iteratively in 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])
``````

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

Using the code below. The idea is that your function needs a "window" of previous values - Kn-6, Kn-4, Kn-2 - and that window can be "slid" along as you compute new values.

So, for some value like "14", you would have a window of K8, K9, ... K13. Just compute using those values, then drop K8 since you'll never use it again, and append K14 so you can use it in computing 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))
``````