/home/wpollock1/public_html/Java/FibonacciMemo.java

// Calculate the n-th Fibonacci number, using a memoized recursive
// method.  (Non-recursive methods are more efficient for this task.)
// Note a Java long will overflow after 92nd Fibonacci number.
// The naive recursive implementation ends up calculating the same values
// over and over.  Instead, we can save previously calculated values and
// just calculate them once.  This technique is called "memoization".
// (To avoid the overflow, use BigInteger objects.)
//
// Usage:  Pass in the number as a command line argument.
//
// Written 11/2016 by Wayne Pollock, Tampa Florida USA

import java.util.Arrays;

class FibonacciMemo
{
   private static long count = 0; // Count of the calls to the method fib
   private static long [] memo;  // Cache of previously calculated values

   public static void main ( String [] args )
   {
      int num = 0;
      try {
         num = Integer.parseInt( args[0] );
         if ( num < 0 )
            throw new IllegalArgumentException( "Must be a positive Integer" );
      } catch ( Exception e ) {
         System.err.println( "Usage: java Fibonacci <num>\n"
            + "\twhere <num> is a positive Integer" );
         System.exit( 1 );
      }

      // Initialize the cache (a value of -1 means "not in cache"):
      memo = new long[(num<2) ? 2 : num+1];  // Ensure memo.length >= 2
      Arrays.fill( memo, -1 );

      // fib(0) = 0 and fib(1) = 1 by definition:
      memo[0] = 0;
      memo[1] = 1;

      System.out.println ( "fib(" + num + ") = "
         + fib( num ) );
      System.out.println( "\nNumber of calls to method fib: " + count );
   }

   /** Calculate the num-th Fibonacci number.
     * <br>Pre-Condition: num >= 0
   */
   private static long fib ( int num )
   {
      ++count;  // Track how many calls are made to this method

      // Check if fib(num) is in the cache:
      if ( memo[num] == -1 )
         // fib(n) is fib(n-1) + fib(n-2) by definition:
         memo[num] = fib( num-1 ) + fib( num-2 );

      return memo[num];
   }
}