FibonacciMemo.java

Download FibonacciMemo.java

 1: // Calculate the n-th Fibonacci number, using a memoized recursive
 2: // method.  (Non-recursive methods are more efficient for this task.)
 3: // Note a Java long will overflow after 92nd Fibonacci number.
 4: // The naive recursive implementation ends up calculating the same values
 5: // over and over.  Instead, we can save previously calculated values and
 6: // just calculate them once.  This technique is called "memoization".
 7: // (To avoid the overflow, use BigInteger objects.)
 8: //
 9: // Usage:  Pass in the number as a command line argument.
10: //
11: // Written 11/2016 by Wayne Pollock, Tampa Florida USA
12: 
13: import java.util.Arrays;
14: 
15: class FibonacciMemo
16: {
17:    private static long count = 0; // Count of the calls to the method fib
18:    private static long [] memo;  // Cache of previously calculated values
19: 
20:    public static void main ( String [] args )
21:    {
22:       int num = 0;
23:       try {
24:          num = Integer.parseInt( args[0] );
25:          if ( num < 0 )
26:             throw new IllegalArgumentException( "Must be a positive Integer" );
27:       } catch ( Exception e ) {
28:          System.err.println( "Usage: java Fibonacci <num>\n"
29:             + "\twhere <num> is a positive Integer" );
30:          System.exit( 1 );
31:       }
32: 
33:       // Initialize the cache (a value of -1 means "not in cache"):
34:       memo = new long[(num<2) ? 2 : num+1];  // Ensure memo.length >= 2
35:       Arrays.fill( memo, -1 );
36: 
37:       // fib(0) = 0 and fib(1) = 1 by definition:
38:       memo[0] = 0;
39:       memo[1] = 1;
40: 
41:       System.out.println ( "fib(" + num + ") = "
42:          + fib( num ) );
43:       System.out.println( "\nNumber of calls to method fib: " + count );
44:    }
45: 
46:    /** Calculate the num-th Fibonacci number.
47:      * <br>Pre-Condition: num >= 0
48:    */
49:    private static long fib ( int num )
50:    {
51:       ++count;  // Track how many calls are made to this method
52: 
53:       // Check if fib(num) is in the cache:
54:       if ( memo[num] == -1 )
55:          // fib(n) is fib(n-1) + fib(n-2) by definition:
56:          memo[num] = fib( num-1 ) + fib( num-2 );
57: 
58:       return memo[num];
59:    }
60: }