Fibonacci numbers (Java)

From LiteratePrograms

Other implementations: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET

Contents 1 Recursion 2 Iteration 3 Memoized recursion 4 Testing

Recursion

This simple java program uses recursion to print the first 10 Fibonacci numbers to the console.

<<Fibonacci.java>>=
public class Fibonacci {
	public static int fib(int n) {
                if (n < 2) {
                   return n;
                }
                else {
		   return fib(n-1)+fib(n-2);
                }
	}
        test main    
}

Iteration

Although it is based directly on the definition of a Fibonacci number, the recursive Fibonacci algorithm is extremely expensive, requiring time O(2ⁿ). It also performs a huge amount of redundant work because it computes many Fibonnaci values from scratch many times. A simple linear-time iterative approach which calculates each value of fib successively can avoid these issues:

<<FibonacciIterative.java>>=
public class FibonacciIterative {
	public static int fib(int n) {
                int prev1=0, prev2=1;
                for(int i=0; i<n; i++) {
                    int savePrev1 = prev1;
                    prev1 = prev2;
                    prev2 = savePrev1 + prev2;
                }
                return prev1;
	}
        test main
}

Note that even this implementation is only suitable for small values of n, since the Fibonacci function grows exponentially and 32-bit signed Java integers can only hold the first 46 Fibonacci numbers.

Memoized recursion

Although the recursive implementation given above is elegant and close to the mathematical definition, it is not very practical. Calculating the nth fibonacci number requires calculating two smaller fibonacci numbers, which in turn require two additional recursive calls each, and so on until all branches reach 1. The iterative solution is faster, but still repeats a lot of calculations when computing successive fibonacci numbers. To remedy this, we can employ memoization to cache previous computations.

We first establish a memoization "cache", which stores previously computed fibonacci numbers. In this case we use an ArrayList, initialized with the first two fibonacci numbers, as the cache. Note that we have also moved from using ints to using Java's BigInteger class, which provides arbitrary-precision integers. As a result, the memoized implementation can also compute much larger fibonacci numbers than the previous solutions (although they too could have been implemented using BigIntegers.

<<Memoization cache>>=
private static ArrayList<BigInteger> fibCache = new ArrayList<BigInteger>();
static {
      fibCache.add(BigInteger.ZERO);
      fibCache.add(BigInteger.ONE);
}

The actual implementation of the fib() function using memoization looks quite similar to the basic recursive function. The difference is that a new fibonacci number is only computed if the cache does not already contain the necessary value. Newly computed fibonacci numbers are added to the cache, so that they become available during later calls to fib().

<<FibonacciMemoized.java>>=
import java.math.BigInteger;
import java.util.ArrayList;
public class FibonacciMemoized {
       Memoization cache
       public static BigInteger fib(int n) {
              if (n >= fibCache.size()) {
                  fibCache.add(n, fib(n-1).add(fib(n-2)));
              }
              return fibCache.get(n);
       }
        test main
}

Testing

We can test all of the above implementations up to this limit using a simple loop:

<<test main>>=
public static void main(String[] args) {
    for (int i=0; i<=46; i++)
        System.out.print(fib(i)+", ");
}

Download code