CODEWITHSUNDEEP
c++algorithm
erwinleonardy
erwinleonardy

Reputation: 486

How to convert a recursive function (with two base cases) to iterative function?

Let's say there is the following recursive function:

int foo (int num)
{
    if (num == 1)
        return an int
    else if (num == 2)
        return another int
    else
        num foo(num-2) + foo(num-1)
}

My Question is:

1) How do you convert the else part into its respective iterative version? I have encountered many functions where the general case is a constant multiplied (or added) by its recursive call. Albeit I have not encountered this scenario before.

else
    return 3 * foo(n-1)

2) Could you give me some tips on how to convert a recursive function to iterative function, especially the one that calls its own function twice and calculates the sum or multiplication of it (like the example on top)?

Thanks a lot.

(EDIT)

Assume that error checking has been done before this function is called. Num is always greater than 0 or (0,∞)

Upvotes: 0

Views: 758

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59154

1)

int foo (int num)
{
    int foo1 = an int;
    int foo2 = another int;
    if (num < 2)
        return foo1;
    for (int n=2; n<num; ++n)
    {
        int foo3 = foo1+foo2;
        foo1 = foo2;
        foo2 = foo3;
    }
    return foo2;
}

2) Iterative implementations often require a deeper understanding of the problem and solution. In this case, I figured out that calculating foo(n) requires calculating all foo(1)...foo(n), and that each one can be done in one step if you remember the preceding two.

Upvotes: 2

Mathias Rav
Mathias Rav

Reputation: 2973

Make a function that fills up a table A where entry A[i] contains the value for foo(i). That is, replace return with A[i] =, and replace recursive calls to foo(i-1) with the lookup A[i-1]. Example code:

int foo (int num)
{
    std::vector<int> results(num+1);
    for (int i = 1; i <= num; ++i) {
        if (i == 1)
            results[i] = an int
        else if (i == 2)
            results[i] = another int
        else
            results[i] = results[i-2] + results[i-1]
    }
    return results[num];
}

Upvotes: 1

Related Questions