Simple Fibonacci using recursion

The sole purpose of this post is to see how a production quality developer would approach this very simple problem. I am a fresh graduate and do not have a professional development experience. What are the cases and approaches that I should start considering when developing in a production environment? Please feel free to provide any suggestion.

public class RecursiveFinonacci {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(getFibonacci(10));
    }

    public static int getFibonacci(int n){
        if(n==0 || n ==1)
            return 1;
        else
            return getFibonacci(n-2) + getFibonacci(n-1);
    }
}

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 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  {
            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 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 (Se

StackExchange Code Review Q#109918, answer score: 15