Iterative version of this recursive function

Question

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)

These are the examples taken from the worksheet and the exact output from the recursive function. — mrpink121
– mrpink121, Commented Nov 11, 2016 at 14:29
Ah, no, my reading skills are mucked up. I'll edit your post to avoid this mistake for others. — Martijn Pieters
– Martijn Pieters, Commented Nov 11, 2016 at 14:36
@MartijnPieters The sum isn't F(n-1) + F(n-2) + F(n-3), it's F(n-1) + 2F(n-2) + 3F(n-3). 1*3 + 2*2 + 3*1 = 10 and 1*10 + 2*3 + 3*2 = 22. — BallpointBen
– BallpointBen, Commented Nov 11, 2016 at 14:37
See, this is why including your own code is important. It gives me to more places to check my assumptions against ;-) — Martijn Pieters
– Martijn Pieters, Commented Nov 11, 2016 at 14:38

Martijn Pieters · Accepted Answer · 2016-11-11 14:37:25Z

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

edited Nov 11, 2016 at 14:37

answered Nov 11, 2016 at 14:19

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

mrpink121 Over a year ago

Thank you! But is there any way to do it without deque? I'm just in the beginning of this Python class in college and our assignment specifically says not to use tools that we haven't covered yet.

Martijn Pieters Over a year ago

You can use a list, then remove the first element and add a new at the end each time: prev = [1, 2, 3] and prev = prev[1:] + [sum(prev)]. That's just not as efficient as a double-ended queue.

mrpink121 Over a year ago

Thank you very much for your help. Unfortunately we have yet to cover lists too. But i got the general idea and I'll try to translate it to something that satisfies my single minded instructor.

Martijn Pieters Over a year ago

Then you could use three variables: Fminus1, Fminus2, Fminus3 = 3, 2, 1 and result = Fminus1 + 2 * Fminus2 + 3 * Fminus3 and Fminus1, Fminus2, Fminus3 = result, Fminus1, Fminus2 and return Fminus1 (untested).

BallpointBen Over a year ago

Great answer Martijn. Very nice that it (the version with the deque) scales to arbitrarily deep recursion without needing to create a variable for each step.

|

Collectives™ on Stack Overflow

Iterative version of this recursive function

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related