Converting recursive algorithm to Iterative


Keywords:python 


Question: 

enter image description here

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.


2 Answers: 

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


I get this answer:

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