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

Licenses and Attributions


Speak Your Mind