-3

I have midterm exams coming up next week and I've come upon a problem that I just can't crack (I find recursion so confusing!). I need to convert this recursive function into an iterative one, I appreciate any help/hints, etc!

The recursive solution: 

long F(int n) {
    if (n >= 0) {
        if (n >= 3) {
            //std::cout << "Current n is: " << n << std::endl;
            long result = 0;
            result = 3 * F(n - 1) + 2 * F(n - 2) + F(n - 3);

            //std::cout << "Current result is : " << result << std::endl;
            return result;
        }
        else  {
            return n;
        }
    }
    else {
        return -1;
    }
}

My attempt at a iterative solution:

long F2(int n) {
    if (n >= 0) {
        long outterResult = 0;
        long innerResult = 0;

        for (int o = n; o >= 3; o--) {
            outterResult += innerResult;
            int iteration = 1;
            for (int i = 3; i > 0; i--) {
                innerResult += i*(n-iteration);
                iteration++;
            }
            //std::cout << "Current n is: " << n << std::endl;
            //std::cout << "Current result: " << outterResult << std::endl;
        }
        return outterResult;
    }
    else {
        return -1;
    }
}

Cheers!

Grandas
  • 519
  • 1
  • 5
  • 13
  • 1
    I will not give out the answer, but all tail recursion can be converted to iteration, see this answer for an explanation: http://stackoverflow.com/a/36985/2063026 – vsnyc Apr 18 '15 at 06:03

1 Answers1

1

In this case dynamic programming approach would do the job - start from the bottom up when n == 0 and store results of sequential values of n in an array. Something like that (it is pseudocode):

 for(int i = 0; i <=n ;++i)
   if( i < 3)
       arr[i]=i;
   else
       arr[i] = 3 * arr[i-1] + 2 * arr[i-2] + arr[i-3]

 return arr[n];
shauryachats
  • 9,975
  • 4
  • 35
  • 48
Dabo
  • 2,371
  • 2
  • 18
  • 26