/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];
}
}