Books / Memoization / Chapter 2
Memoization Examples in Java
Here’s a complete example of Fibonacci sequence in Java with and without Memoization. The calls are also instrumented to measure how long it takes to run each algorithm.
Here’s the complete source code.
public class FibonacciNumbers {
public static void main(String args[]) {
int num = 40;
// Run simple Fibonacci with recursion and measure the time
long startTime = System.currentTimeMillis();
int r = fib(num);
long endTime = System.currentTimeMillis();
System.out.println("fib(" + num + ") = " + r + ". Took " + (endTime - startTime) + " milliseconds" );
// Run simple Fibonacci with memoization and measure the time
startTime = System.currentTimeMillis();
r = fibMemo(num, new int[num+1]);
endTime = System.currentTimeMillis();
System.out.println("fibMemo(" + num + ") = " + r + ". Took " + (endTime - startTime) + " milliseconds");
}
/**
* Simple Fibonacci with Recursion
* See https://codeahoy.com/learn/memoization/ch1/
*/
public static int fib(int n) {
if (n <= 1) {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}
/**
* Simple Fibonacci with Recursion using Memoization
* See https://codeahoy.com/learn/memoization/ch1/
* @param n
* @param memo Memoization lookup table for storing intermediate results
*/
public static int fibMemo(int n, int[] memo) {
if (n <= 1) {
return n;
} else {
int result = memo[n];
if (result == 0) { // If the result doesn't exist in array, calculate and store it
result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo[n] = result;
}
return result;
}
}
}