CODEWITHSUNDEEP
javarecursionfibonacci
kebrown4
kebrown4

Reputation: 25

Optimizing a recurisive fibonacci method.

I'm trying to optimize a fibonacci recurisve method so that it isn't as slow as the recursive method. The parameters of the these methods have to be as such. Whenever I run this it isn't giving me the result I need. Any suggestions on how to move forward would be helpful.

      public static long optimizedFib(int n)
      {
          long[] parameters = new long[3];
          for(int i =0; i < n;i++)
          {
             parameters[i] = 1;
          }
          return optimizedFib(n, parameters);
      }

public static long optimizedFib(int n, long[] parameters)
{
    if(n <= 2)
    {
        return 1;
    }
    else
    {   
    parameters[2] = parameters[1] + parameters[0];
    parameters[1] = parameters[0]; 
    parameters[0] = parameters[2];
    }
    return optimizedFib(n-1, parameters);
}

}

Upvotes: 1

Views: 1003

Answers (1)

Ryan Emerle
Ryan Emerle

Reputation: 15811

First, you're blowing past the bounds of your array. You define your array with a size of 3:

long[] parameters = new long[3];

Then you iterate to n

for(int i =0; i < n;i++)
{
    parameters[i] = 1;
}

You also initialize your values to 1, which is incorrect. Since you only use three indexes, and we need only the first index to be 1, we can simply initialize the first index to 1 (the remaining values will default to 0).

public static long optimizedFib(int n)
{
    long[] parameters = new long[3];
    parameters[0]=1;
    return optimizedFib(n, parameters);
}

Next, your recursive method never returned the result of the calculation (it only ever returned 1). To fix that, we recursively call optimizedFib then return the sum of parameters[0] and parameters[1].

public static long optimizedFib(int n, long[] parameters)
{
    if(n <= 0){
        return 0;
    }
    if(n <= 2)
    {
        return 1;
    }
    else
    {
        parameters[2] = parameters[1] + parameters[0];
        parameters[1] = parameters[0];
        parameters[0] = parameters[2];
        optimizedFib(n-1, parameters);
        return parameters[0] + parameters[1];
    }
}

Note that you will overflow the long datatype when n > 92.

Additional Information

This optimization is called Memoization. You can see more implementations here. There an iterative solution which, in my opinion, is a bit easier to grok:

public int fib(int n) {
    if (n < 2) {
        return n;
    }
    int[] f = new int[n+1];
    f[0] = 0;
    f[1] = 1;
    for(int i = 2;i<=n;i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

Source

Upvotes: 1

Related Questions