CODEWITHSUNDEEP
javaalgorithmrecursioniteration
MWin123
MWin123

Reputation: 1485

Multiple recursion to iteration

I'm learning Java and for an exercise I have to implement a recursive and an iterative method that return the following for a positive integer.

L(0) = 1
L(1) = 1
L(n) = L(n - 1) + L(n - 2) + 1  if  n > 1

The recursive method was no problem.

public static int rec (int n) {
    if (n > 1) {
        return rec (n-1) + rec(n-2) + 1;
    }
    else {
        return 1;
    }
}

I can convert simple recursion to iterations and vice versa, but I don't know how to solve this one. Do you have any tips?

Edit: Thanks for the tip with the Fibonacci Sequence. I got it now:

public static int iter (int n) {
    int f0 = 1;
    int f1 = 1;
    int fn = 0;

    if (n > 1) {
        for (int i = 1; i < n; i++) {
            fn = f0 + f1 + 1;
            f0 = f1;
            f1 = fn;
        }
    }
    else {
        return 1;
    }
    return fn;
}

Upvotes: 2

Views: 595

Answers (3)

Luis Lavieri
Luis Lavieri

Reputation: 4109

Here is my version

public static int modifiedFibonacci(int n)
{
   if(n > 1){
       int f1 = 0;
       int f2 = 0;
       int result = 0;
       for (int i = 2; i <= n; i++)
       {
          result = f1 + f2 + 2;
          f2 = f1;
          f1 = result;
       }
       return ++result;
   }
   return 1;
}

Upvotes: 0

null
null

Reputation: 3517

why are you +1 for fib?

0,1,1,2,3,5,8,11 if I recall correctly, the sum of the previous 2 numbers assuming that n is greater than 1.

shouldn't it be something like:

int fib(int n){
if (n == 0){
       return 0;
   } else if (n == 1) {
       return 1;
   } //base case
   else{
       return fib(n-2)+fib(n-1);
   }

apologies if the code isn't perfect but you should get the idea.

The other answer to the iterative approach works fine, this is just to highlight the +1 with code and shouldn't be the accepted answer :)

Upvotes: 0

Piyush Aghera
Piyush Aghera

Reputation: 965

Try with simply with two variable.

    public static int rec1(int n) {

    int result=0;
    int previous1=0;
    int previous2=0;

    int i=0;
    while(i<=n)
    {
        if(i==0 || i==1)
        {
            result=1;
        }
        else
        {
            result= previous1 + previous2 + 1;
        }

        previous2=previous1;
        previous1=result;
        i++;
    }
    return result;
}

Upvotes: 4

Related Questions