HaimLeshem - 1 year ago 68
Python Question

# Iterative version of this recursive function

I have a function that is defined in this way:

`F(n) = n`
`if n<=3`

`F(n) = F(n-1) + 2 * F(n-2) + 3 * F(n-3)`
`if n>3`

Now, I've written it as a recursive function and it works fine.
I'm trying to write it as an iterative function but i cant seem to make it happen.

The output should be, for example:

``````print(FRec(5))    => 22
print(FRec(10))  => 1657
print(FRec(15))  => 124905
``````

Any tips?

Here is my recursive implementation:

``````def FRec(n):
if(n <= 3):
return n
if(n > 3):
return FRec(n - 1) + 2 * FRec(n - 2) + 3 * FRec(n - 3)
``````

All you need is keep the last 3 results:

``````from collections import deque

def F_iter(n):
if n <= 3:
return n
prev = deque([1, 2, 3], maxlen=3)
for i in range(4, n + 1):
result = prev[-1] + 2 * prev[-2] + 3 * prev[-3]
prev.append(result)
return prev[-1]
``````

If a `deque` is not 'available' to you, then you can inefficiently replace that with some list slicing and concatenation:

``````    prev = [1, 2, 3]
for i in range(4, n + 1):
result = prev[-1] + 2 * prev[-2] + 3 * prev[-3]
prev = prev[1:] + [result]
``````

Demo:

``````>>> F_iter(5)
22
>>> F_iter(10)
1657
>>> F_iter(15)
124905
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download