CODEWITHSUNDEEP
algorithmrecursioniteration
Bryan
Bryan

Reputation: 8697

Converting a recursive function that return 2 recursion to Iteration

I always have problem trying to convert a recursive algorithm which i created that returns 2 recursive call until the base case is met.

It's easy to like track back what each recursive call do but converting them to iteration is a little confusing.

For example this recursive function

BEGIN SEQ(n)
   if (n == 1)
     return 3;
   
  else if (n == 2)
     return 2;

  else 
     return SEQ(n - 2) + SEQ(n - 1)

This is rather straight forward when i try to rubber duck my way through the recursive which produces the follow process

SEQ(6) = SEQ(4) + SEQ(5)

SEQ(5) = SEQ(3) + SEQ(4)

SEQ(4) = SEQ(2) + SEQ(3)

SEQ(3) = SEQ(1) + SEQ(2)

SEQ(2) = 2

…

SEQ(3) = 3 + 2 = 5

SEQ(4) = 2 + 5 = 7

SEQ(5) = 5 + 7 = 12

SEQ(6) = 7 + 12 = 19

However, i can't seems to figure out an iteration way that return exactly how the recursive does

Upvotes: 2

Views: 71

Answers (1)

αNerd
αNerd

Reputation: 528

Your iteration method in C# could look like this:

public static int SEQ(int n)
{
    if (n == 1)
    {
        return 3;
    }

    if (n == 2)
    {
        return 2;
    }
    var first = 3;
    var second = 2;

    for (var i = 3; i <= n; i++)
    {
        second += first;
        first = second - first;
    }


    return second;
}

Upvotes: 4

Related Questions