12
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • 12
    \$\begingroup\$ A professional developer would usually not do Fibonacci numbers, as we're normally too buzy doing other work... With exception of here on Code Review I can't remember the last time I saw stuff related to Fibonacci numbers! \$\endgroup\$ – holroy Nov 5 '15 at 21:28
  • \$\begingroup\$ This will be extremely slow for everything but the smallest of numbers. Try printing something like 50 factorial, and see what I'm talking about. If you use a loop rather than recursion, it will still be fast with very large numbers. \$\endgroup\$ – DJMcMayhem Nov 6 '15 at 1:49
  • 1
    \$\begingroup\$ Avoid recursion and loops altogther: Binet's formula maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/… \$\endgroup\$ – Julia Hayward Nov 6 '15 at 13:07
  • \$\begingroup\$ Maybe this kind of job requires working with algorithms or kind mathematical computer since, I have yesterday presented a Dynamic Programming way in stead of recursion, a poor guy down voted my answer, I have also delete my answer. \$\endgroup\$ – maytham-ɯɐɥʇʎɐɯ Nov 6 '15 at 13:42
  • 1
    \$\begingroup\$ This isn't so much a software design principle as a mathematical remark, but one thing I haven't seen mentioned in previous answers is the existence of an explicit closed-form expression that directly computes the n<sup>th</sup> Fibonacci number: $$ F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right] $$ You might recognize that \$\frac{1 + \sqrt{5}}{2} = \phi\$ is the famous golden ratio. \$\endgroup\$ – David Zhang Nov 26 '15 at 7:34
14
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ You're better off with an array rather than a hashmap. 40 iterations is not nearly enough. And it's highly questionable to do microbenchmarks interwoven like that. Not only is the JIT probably going to make the first results take longer than the later ones, but thread contention will seriously impact your results. \$\endgroup\$ – Eric Stein Nov 5 '15 at 20:10
  • \$\begingroup\$ @EricStein The benchmark clearly shows the problem in having to recalculate the Fibonacci number every time. Execution time for the memoization based method is ~0ms and ~1013ms for the recursive call on my machine. The low iteration count is simply because for higher iterations, his version takes more and more time (42 = 2.7s, 43 = 4.4s, etc.) \$\endgroup\$ – user2296177 Nov 5 '15 at 20:25
  • \$\begingroup\$ I don't think anybody disputes that memoizing is better than not memoizing. \$\endgroup\$ – Eric Stein Nov 5 '15 at 20:55
  • \$\begingroup\$ @EricStein I must have misunderstood what you meant by "40 iterations is not nearly enough". Enough for what? \$\endgroup\$ – user2296177 Nov 5 '15 at 21:00
  • \$\begingroup\$ To get a valid benchmark for about how long something takes. If you're trying to prove that memoizing is much faster, then yes, you've done that, but only because the disparity is so large. 40 iterations isn't enough for the JIT to shake out its optimizations, so for any non-obvious comparision, you need more iterations. \$\endgroup\$ – Eric Stein Nov 5 '15 at 21:03
7
\$\begingroup\$
  1. You should be validating your input, and you don't address overflow at all on your computation.
  2. You have no javadoc. The javadoc should clearly indicate what the method does, what inputs are acceptable, what happens for invalid output, and what outputs may occur - including a discussion on what happens in overlow situations.
  3. Leaving the Eclipse-generated TODO in there is a clear indication this code was slapped together. Details are important.
  4. Your spacing is inconsistent.
  5. You should always include {}, even if they are not required. This is important for clarity and prevention of future bugs.
  6. Recursion is an inefficient solution to the problem of "give me fibonacci(n)". Assuming recursion is mandatory, you can either trade memory for performance by memoizing previously computed values so they aren't recomputed or by adding a helper method which accepts previously computed values. If recursion is not mandatory, use a variation of @TopinFrassi's iterative solution.

If I were to write a non-recursive, memoizing fibonacci calcuator, it would look like:

private BigInteger[] memoizedValues = new BigInteger[] { BigInteger.ZERO, BigInteger.ONE };

public BigInteger fibonacci(final int n) {
    if (n < 0) {
        throw new IllegalArgumentException("Argument must be >= 0, was " + n);
    }

    if (n < this.memoizedValues.length) {
        return this.memoizedValues[n];
    }

    final BigInteger[] newMemoizedValues = new BigInteger[n + 1];
    System.arraycopy(this.memoizedValues, 0, newMemoizedValues, 0, this.memoizedValues.length);
    for (int i = this.memoizedValues.length; i < newMemoizedValues.length; i++) {
        newMemoizedValues[i] = newMemoizedValues[i - 1].add(newMemoizedValues[i - 2]);
    }

    this.memoizedValues = newMemoizedValues;
    return this.memoizedValues[n];

}

Using BigInteger handles the overflow issues. Memoizing saves on computations. Linear calculation removes stack overflow issues. Using an array instead of a map is 2x as fast when given random inputs and fractionally slower when given linear inputs in a loop.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is a good solution, but I would advise against having the Fibonacci method also take care of resizing the array (from a design point) because that has nothing to do with actually calculating the Fibonacci number. Those are two separate functionalities. \$\endgroup\$ – user2296177 Nov 5 '15 at 21:07
7
\$\begingroup\$

It's a good way to express the Fibonacci's recurrence relation. Though, it isn't very efficient!

Imagine steps to get getFibonacci(7)

  1. getFibonacci(5) + getFibonacci(6)
  2. getFibonacci(3) + getFibonacci(4) + getFibonacci(4) + getFibonacci(5)
  3. getFibonacci(1) + getFibonacci(2) + getFibonacci(2) + getFibonacci(3) + getFibonacci(2) + getFibonacci(3) + getFibonacci(3) + getFibonacci(4)
  4. 1 + getFibonacci(0) + getFibonacci(1) + getFibonacci(0) + getFibonacci(1) + getFibonacci(1) + getFibonacci(2) + ...

You know what, I won't write it. It's super long and you got the point! :p

This is an \$O(\phi^n)\$ operation, which is pretty super slow. The performance of such an algorithm get's terrible real quick. (Check out the comments to see the mistake I made! :p)

  • getFibonacci(2) requires 4 operations
  • getFibonacci(10) requires ~\$2^{10}\$ operations (and 10 is a small number)
  • getFibonacci(23) requites ~\$2^{23}\$ or ~8388608 operations operations!
  • etc..

It's long, you get it! :p

Now, you have two options. Either you use the iterative approach, which is probably the best solution because it computes Fibonacci's number much faster, using summations of previous values to get a result.

public static int getFibonacci(int n){
    int a = 0;
    int b = 1;

    while(n != 1) {
        int temp = b;
        b += a;
        a = temp;
        n--;
    }
    return b;
}

(This may not be the best implementation ever, but eh, it works!)

Or you keep your well written recursive function! :p Because there's nothing to say about your code other that it's perfect in its purpose.

Nitpicking : You might want to check that n isn't a negative number!

\$\endgroup\$
  • \$\begingroup\$ You've gotten mixed up in your runtime analysis. This isn't O(n^2); it's O(phi^n), where phi is the golden ratio. O(2^n) (not O(n^2)) would be a valid upper bound, but saying that getFibonacci(23) takes 2^23 operations is wrong. \$\endgroup\$ – user2357112 Nov 5 '15 at 20:26
  • \$\begingroup\$ @user2357112 Hmm yeah you're right! Thanks, I wrote n^2 but I meant 2^n, which isn't it anyways lol \$\endgroup\$ – IEatBagels Nov 5 '15 at 20:28
4
\$\begingroup\$

To follow up TopinFrassi's answer, naive recursion is very inefficient and should not be considerer for a production version of fib. You will start encountering stack overflows for relatively small n (>5000). This holds at least in the Java world.

In languages that have tail-recursion optimisation, recursion might be an acceptable substitute for iteration.

\$\endgroup\$
  • 1
    \$\begingroup\$ I noticed overflows start happening at getFibonacci(46) : -1323752223 good pointing this out \$\endgroup\$ – Phrancis Nov 5 '15 at 20:10
  • 4
    \$\begingroup\$ @Phrancis That's due to integer overflow, not stack overflow. \$\endgroup\$ – user2296177 Nov 5 '15 at 20:14
  • \$\begingroup\$ Oh, my mistake, I misread that. \$\endgroup\$ – Phrancis Nov 5 '15 at 20:20
  • 2
    \$\begingroup\$ Still, it's a valid concern :p \$\endgroup\$ – IEatBagels Nov 5 '15 at 20:33
4
\$\begingroup\$

A simple but much faster recursive solution would be:

public static int fib(int n) {
    assert n >= 0;
    return fibHelper(0, 1, n);
}

private static int fibHelper(int a, int b, int k) {
    return k == 0 ? a : fibHelper(b, a + b, k - 1);
}

Now you could use a loop instead of the helper function (see TopinFrassi's solution), but I don't think there are big differences. Of course recursive code can lead to stack overflows, but this is no problem here, because Fibonacci numbers grow so fast that they reach MAX_INTEGER long before that happens.

If you decide to use BigIntegers instead, it would be a completely different story. In that case you should use the following much faster formulas:

fast Fibonacci formulas

(from https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form )

\$\endgroup\$
  • \$\begingroup\$ That's what I used when I've been asked to write a fibonacci's recursive algorithm in interview. Weirdly, they chose me lol. \$\endgroup\$ – IEatBagels Nov 5 '15 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.