Recursive Fib style function into Iterative?

Question

I have a function in java which is written with a recursive algorithm that needs to be written in Iterative form. The thing is that I dont know where to start in wrapping my mind around a new algorithm for this. This is an assignment I am working on.

Consider the following computational problem:

Suppose you work as a consultant and you have a sequence of n potential consulting jobs that pay A[0],A[1],..,A[n-1] dollars, respectively (so job 0 pays A[0] dollars, job 1 pays A[1] dollars, etc.).

Also, job i starts on day i (i = 0 ; : : : ; n 1 ).

However, each job requires 2 days, so you cannot perform any two consecutive jobs. The goal is to determine the maximum amount of money, denoted by F(n) ; you can earn from a valid job schedule selected from the n jobs A[0] through A[n-1] : As an example, consider the following input array:

  0 1 2 3 4 5
A 5 6 8 6 2 4

An optimal schedule is to do jobs 0 ; 2 ; and 5 ; for which the amount of money earned, F(6) = A[0] + A [2] + A [5] = 17 ; is as large as possible. Notice that this is a valid schedule, as no two consecutive jobs are included.

My function for the recursive version that solves this is as follows:

public static int jobScheduleRecursive(int[] A, int n) 
{
    n = A.length;
    if(n == 0){return 0;}
    else if(n == 1){return A[0];}
    else if(n >= 2){return max(jobScheduleRecursive(A, (n-1)), (A[n-1]) 
                           + jobScheduleRecursive(A, n-2));}
    else return -1;
}

To sum up, I have to come up with an iterative algorithm that does this job. The only problem is that i have no idea how to proceed. I would appreciate any advice to lead me in the right direction.

Why do you take an argument and then immediately set its value? Why take it in the first place? — mowwwalker, Oct 04 '11 at 05:52
possible duplicate of [Can every recursion be converted into iteration?](http://stackoverflow.com/q/931762/), [Design patterns for converting recursive algorithms to iterative ones](http://stackoverflow.com/q/1549943/) — outis, Jun 20 '12 at 22:43

score 1 · Accepted Answer · answered Oct 04 '11 at 05:58

sometimes, iterative solutions for a known recursive solution to problems isn't straight forward as the recursive solution. The easiest way to achieve iterative solution is to use - Dynamic Programming basically what you want is to create a temporary array that holds the solution to all sub-problems in the way. to achieve that, create a dynamically allocated array in the size of your input. and if for instance your recursive function is int foo(int a) fill the array with the solutions to 1..n, where n is the input for your original problem. change the algorithm, that instead of calling itself recursivelly, it will check if the solution for the sub-problem allready exists in the array, if not, it fills it up. that way a sub-problem won't compute numerus times, but only once.

Recursive Fib style function into Iterative?

1 Answers1