CODEWITHSUNDEEP
javaalgorithmrecursioniteration
Rorie
Rorie

Reputation: 23

Turn a recursive method into an iterative method

I have to create two methods that do the same thing. The methods have to calculate the L(n) of the numbers from 0 - 30 where L(n) is defined as

L(0) = 1

L(1) = 1

L(n) = L(n - 1) + L(n - 2) + 1; when n > 1

The first method has to be written using recursion which I successfully did and the second one has to be made using iteration ( arrays and for loops ) First method)

public static int rec(int x) {
  if (x == 0) return 1;
  if (x == 1) return 1;
  else return rec(x - 1) + rec(x - 2) + 1;
}

and i added this in main for the first method

int x = 0;
    while (x <= 30) {
        System.out.println(rec(x));
        x++;
    }

and this is all i have been able to do with the second method , while i know it is wrong , bare in mind im a beginner , be gentle Second method)

 public static long iter(long [] x){
    long result = 0  ;
    int length = x.length;
    for ( int i = 0 ; i < length ; i++){
        if ( i == 0 ) result = 1;
        if ( i == 1 ) result = 1;
        else  result += x[i-1]+x[i-2]+1;
    }
    return result ;
}

Upvotes: 0

Views: 210

Answers (4)

Rorie
Rorie

Reputation: 23

So I was able to finally solve it : ( Thanks for all the help , really really appreciate it )

public class Aufgabe1 {

// invokes iter as well as rec with all integers from 0 to 30 and prints the results
// (without empty lines or other output)
public static void main(String[] args) {
    // TODO: Implementation is your task
    int x = 0;
    while (x <= 30) {
        System.out.println(rec(x));
        x++;
    }
    long [] longArr = new long[31];
    iter(longArr);
}

public static int rec(int x) {
    if (x == 0) return 1;
    if (x == 1) return 1;
    else return rec(x - 1) + rec(x - 2) + 1;
}

    public static void iter(long[] n) {
        for (int i = 0; i < n.length; i++) {
            if (i == 0 || i == 1) {
                n[i] = 1;
            } else {
                n[i] = n[i - 1] + n[i - 2] + 1;
            }
            System.out.println(n[i]);
        }

    }
    }

Upvotes: 0

OldCurmudgeon
OldCurmudgeon

Reputation: 65803

You are very close - you need to hold a history in your iterating solution:

public static long iter(long x) {
    long result = 0;
    // Make a 2-length array for my history.
    long[] history = new long[2];
    for (int i = 0; i <= x; i++) {
        if (i < 2) {
            result = 1;
        } else {
            result = history[0] + history[1] + 1;
        }
        // Maintain my history.
        history[0] = history[1];
        history[1] = result;
    }
    return result;
}

Upvotes: 0

nitegazer2003
nitegazer2003

Reputation: 1193

How about treating L as an array, then performing the following assignments:

L(0) = 1

L(1) = 1

For the 3rd step, you will have to write a loop calculating and storing the values of L[2] to L[30]. At each iteration of the loop, the previous 2 values will already be in L, so you can just use them.

Upvotes: 1

Hari Reddy
Hari Reddy

Reputation: 3858

Think about what your code here is doing - 

for ( int i = 0 ; i < x.length ; i++){
           long returnvalue = x[i-1]+x[i-2]+1; // every iteration you are resetting returnvalue. 
    }

In every iteration you are creating a new variable and then losing what you have just computed. You need to add this result from each iteration so you will have to do this - 

 for ( int i = 0 ; i < x.length ; i++){
           returnvalue = returnvalue + x[i-1]+x[i-2]+1;
    }

Or you can also do this - 

returnvalue +=  x[i-1]+x[i-2]+1;

Notice that in the iterative version returnValue is defined only once before your loop starts.

Upvotes: 1

Related Questions