CODEWITHSUNDEEP
pythonfunctionrecursioniteration
King James
King James

Reputation: 45

How would I write this recursive function iteratively?

In Python:

def g(n):  
    if n <=3:        
        return n   
    return g(n-1) + 2 * g(n-2) + 3 * g(n-3)

I understand what this function is doing, but I can't seem to get how to make it iterative. Help, please. If possible, please include an explanation so that I could fully understand the problem.

Upvotes: 1

Views: 2545

Answers (4)

Jonas Sch&#228;fer
Jonas Sch&#228;fer

Reputation: 20718

This looks similar to the fibonacci series problem and is non-trivial to implement in an iterative fashion. It also looks like homework, so I will be posting the steps to get fibonacci iterative and you should be able to apply that to your problem.

In case you do not know, fibonacci is defined like this:

def fib(n):
    if n <= 1:  # technically, this is not 100% correct, but it's fine for n>=0
        return n
    return fib(n-1) + fib(n-2)

So let's analyze fib(n). First we see that there are two different cases: n <= 1 and not n <= 1. For n <= 1, fib(n) has no dependencies, so we can just evaluate that:

def fib_iter(n):
    if n <= 1:
        return n

Now we need to cover the other case. Let's first do a dependency analysis. What do we need for fib(n) with n > 1? We call to fib(n-1) and fib(n-2). In iterative language, these would be the two previous values. So obviously, we need to keep track of those. We will start with the two trivial cases on that one:

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1

I hope this is rather obvious. Then we resolve the functions in the order they are resolved in the recursive approach. When unwinding the recursion and analyzing the function, we find that the first non-trival value which will be evaluated is of course fib(2). Then fib(3) and so on until we reach n. Due to the recursive approach, several values are evaluated multiple times, but we do not need that in an iterative approach. The values are added together, which gives us the following code:

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1
    for i in xrange(2, n+1):
        curr = prev1 + prev2        # calculate fib(i)
        prev1, prev2 = prev2, curr  # shift previous value cache

The only thing which is missing is the return value, which is just curr at the time the loop ends. As we do xrange(2, n+1) and check for n <= 1 in advance, the loop will run at least once, so curr will be defined outside the loop.

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1
    for i in xrange(2, n+1):
        curr = prev1 + prev2
        prev1, prev2 = prev2, curr
    return curr

(this is my first homework answer; the SO community might give me feedback what I could've done better if I spoiled too much)

Upvotes: 8

Hugh Bothwell
Hugh Bothwell

Reputation: 56654

Your recursive function can be read as

To find the value of g(30), find the value of g(29), g(28), and g(27)
  To find the value of g(29), find the value of g(28), g(27), and g(26)
    To find the value of g(28), find the value of g(27), g(26), and g(25)
      ...
        (repeat until all sub-finds have completed)

An iterative function would start at the other end,

I know the values of g(1), g(2), and g(3) -> calculate g(4)
I know the values of g(2), g(3), and g(4) -> calculate g(5)
I know the values of g(3), g(4), and g(5) -> calculate g(6)
...
(repeat until the desired g(n) is reached)

Upvotes: 3

Aleksei astynax Pirogov
Aleksei astynax Pirogov

Reputation: 2491

def g(n):
    if n <= 3:
        return n
    a, b, c = 1, 2, 3
    for i in range(3, n):
        a, b, c = b, c, (a * 3 + b * 2 + c)
    return c

Upvotes: 4

Noctis Skytower
Noctis Skytower

Reputation: 22001

This was too much fun not to solve ...

def g(n, *, _cache=[0, 1, 2, 3]):
    for _ in range(n - len(_cache) + 1):
        _cache.append(sum(i * _cache[-i] for i in (1, 2, 3)))
    return _cache[n]

Hopefully, you will have already found a solution.

Upvotes: 1

Related Questions