Fibonacci Sequence

Here's an interesting usage of "memoization". According to Wikipedia, "In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.".

There is actually a drawback if we are using plain and simple recursion to compute the Fibonacci sequence using long datatype (because we are only limited to hold the first 48 Fibonacci numbers). Memoization helps to speed up the computation time by saving already computed values into memory (and we can use BigInteger datatype). An example implementation is as below:

import java.math.BigInteger;
import java.util.ArrayList;

public class Fibonacci {

  /** Variables for memoization **/
  private static ArrayList fibMemoized = new ArrayList();
  static {
    fibMemoized.add(BigInteger.ZERO);
    fibMemoized.add(BigInteger.ONE);
  }

  /** Memoized method to retrieve stored computed values **/
  public static BigInteger fibonacci(int n) {
    if (n >= fibMemoized.size()) {
      fibMemoized.add(n, fibonacci(n-1).add(fibonacci(n-2)));
    }
    return fibMemoized.get(n);
  }

  /** Old school recursion **/
  public static long fib(int n) {
    if (n <= 1) return n;
    else return fib(n-1) + fib(n-2);
  }

  /** Driver **/
  public static void main(String[] args) {
    int N = 45;
    System.out.println(fibonacci(N));
    System.out.println(fib(N));
  }

}

You may try copying the codes and run it locally to observe the difference in performance. The typical recursive method runs slower because it computes the Fibonnaci numbers from scratch many times. Unlike the memoized method, the ArrayList is used to store the previously computed values. While memoized method is more superior in terms of speed, we are actually sacrificing space in order to achieve greater speed.