CODEWITHSUNDEEP
pythonrecursioniteration
user7588893
user7588893

Reputation:

Converting recursive algorithm to Iterative

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.

Upvotes: 1

Views: 724

Answers (2)

benedemon
benedemon

Reputation: 429

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

Upvotes: 1

aghast
aghast

Reputation: 15310

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

Upvotes: 0

Related Questions