Since you are asking what are the cases to consider, I'll give you a very simple one. Following that, there is a further refinement to achieve a final solution as well as a few comments to consider.
Trading space for speed using memoization
Definition: https://en.wikipedia.org/wiki/Memoization
Basically, we want to keep a look-up table of Fibonacci numbers that we've already computed in order to avoid computing them again. We can also obtain newer Fibonacci numbers by simply using the pre-computed values that we've already evaluated.
package codereview;
import java.util.HashMap;
public final class FibonacciNumber {
/**
* A O(1) look-up table to store Fibonacci numbers
*/
private static HashMap<Integer, Integer> computedFibonacciNumbers = new HashMap<>();
/**
* Calculates the n-th Fibonacci number by using memoization
*
* @param n
* n-th Fibonacci number to calculate
* @return n-th Fibonacci number
*/
public static int getFibonacci( final int n ) {
// check for Fibonacci numbers that have already been computed
if ( computedFibonacciNumbers.containsKey( n ) ) {
return computedFibonacciNumbers.get( n ).intValue();
}
if ( n == 0 || n == 1 ) {
return 1;
} else {
// calculate it
Integer nFibonacciNumber = getFibonacci( n - 2 ) + getFibonacci( n - 1 );
// insert it into our look-up table
computedFibonacciNumbers.put( n, nFibonacciNumber );
return nFibonacciNumber.intValue();
}
}
}
For example, this will greatly increase the speed of computing successive Fibonacci numbers.
Here is a timed test that should show you the difference:
package codereview;
import java.lang.Runnable;
public class Main {
public static void main( String[] args ) {
int loops = 40;
Runnable memoizationCompute = () -> {
int last = 0;
for ( int i = 0; i < loops; ++i )
last = FibonacciNumber.getFibonacci( i );
System.out.println( "fibonacci = " + last );
};
Runnable alwaysCompute = () -> {
int last = 0;
for ( int i = 0; i < loops; ++i )
last = getFibonacci( i );
System.out.println( "fibonacci = " + last );
};
System.out.println( timeExecutionMilliseconds( memoizationCompute ) );
System.out.println( timeExecutionMilliseconds( alwaysCompute ) );
}
public static long timeExecutionMilliseconds( Runnable r ) {
long timeBegin = System.nanoTime();
r.run();
long timeEnd = System.nanoTime();
return ( timeEnd - timeBegin ) / 1000000;
}
public static int getFibonacci( int n ) {
if ( n == 0 || n == 1 )
return 1;
else
return getFibonacci( n - 2 ) + getFibonacci( n - 1 );
}
}
The problems of recursiveness
However, while this highlights an optimization to your current solution, there are better alternatives. You should usually consider implementing recursive algorithms as non-recursive because this will result in better speed and will also allow for higher values of n, since you will get a java.lang.StackOverflowError when you try to compute it recursively for modest values of n.
A final solution?
Knowing all this, we can combine both approaches in order to get the benefits of the iterative solution and the benefits of storing precomputed values. This is good if you will be constantly accessing Fibonacci numbers in a range.
Source of iterative algorithm: http://en.literateprograms.org/Fibonacci_numbers_(Java)#Iteration
package codereview;
import java.util.HashMap;
public final class FibonacciNumber {
/**
* A O(1) look-up table to store Fibonacci numbers
*/
private static HashMap<Integer, Integer> computedFibonacciNumbers = new HashMap<>();
/**
* Calculates the n-th Fibonacci number by using memoization
*
* @param n
* n-th Fibonacci number to calculate
* @return n-th Fibonacci number
*/
public static int getFibonacci( final int n ) {
// check for Fibonacci numbers that have already been computed
if ( computedFibonacciNumbers.containsKey( n ) ) {
return computedFibonacciNumbers.get( n ).intValue();
}
int prev1 = 0, prev2 = 1;
for ( int i = 0, hi = n + 1; i < hi; i++ ) {
int savePrev1 = prev1;
prev1 = prev2;
prev2 = savePrev1 + prev2;
}
computedFibonacciNumbers.put( n, prev1 );
return prev1;
}
}
Implementation remarks
While this is working code, there is still work to be done in order to make this more efficient. I'll leave the implementation of most comments in the following section to you.
Other comments
- Can you get even better performance by using a simpler data structure? See this comment for a suggestion. It entails using
n as the index of the array.
- Is the
int type really sufficient for computing Fibonacci numbers? We note that it starts to overflow for n >= 46 (See this comment in another answer). You might want to use BigInteger.
- What happens with invalid values of
n (negative values)? Do you assume users are responsible enough to use the method correctly (I would, but this is subjective).
- Mark constant variables as
final. n is never modified it should thus be marked as final to indicate so to users. It is clearer and less error-prone in the sense that you won't modify it by mistake.
- You will most definitely want to provide Javadoc in production code. You should also do it for your own code, as it can clearly define what the operation does without having you read through the code. You can look at my Javadoc for a very basic documentation of the method.
- Is there a more efficient way of doing the calculation? See this answer for a way and this comment for possibilities.
