1

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.

Improve this question
6
  • 3
    Don't imitate a stack, use a stack. :) Commented Apr 16, 2017 at 19:02
  • I think the goal of your math exercice is to compute a few values of Kn recursively and then to try to find a non-recursive form using the computed values. In short, it's a math problem, not a Python one Commented Apr 16, 2017 at 19:06
  • 1
    memoization would be exceptionally useful in this function Commented Apr 16, 2017 at 19:08
  • 2
    Have you ever written an iterative Fibonacci algorithm? Use the same idea. Commented Apr 16, 2017 at 19:10
  • 1
    I suggest you to try out yourself until it hangs your brain. This'll make you a better programmer. Think more about what @user2357112 and Kenny Ostrom said. Commented Apr 16, 2017 at 19:23

2 Answers 2

Reset to default
1

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])
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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))
Improve this answer

1 Comment

I don't think we should be posting finished answers to easy homework problems. Also, I used an even/odd check to get the starting numbers, and avoid computing half of the values.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.