SimpleFib.java

import java.math.BigInteger;

public class SimpleFib {
  public static void main(String[] args) {
    if (args.length != 1) {
      System.err.println("Usage: a single positive java integer representing Fibonacci sequence number");
      System.exit(1);
    }
    int n = Integer.parseInt(args[0]);
    System.out.println("Recursive: " + recursiveFib(n));
    System.out.println("Recursive but memoized: " + recursiveFibMemoize(n, null));
    System.out.println("Iterative: " + iterativeFib(n));
  }

  /**
   * time: O(2^n)
   */
  public static BigInteger recursiveFib(int n) {
    if (n < 0) throw new IllegalArgumentException("N can not be negative");
    else if (n == 0) return BigInteger.ZERO;
    else if (n == 1) return BigInteger.ONE;
    else return recursiveFib(n-1).add(recursiveFib(n-2));
  }

  /** 
   * time: O(n) extra space: O(n)
   */
  public static BigInteger recursiveFibMemoize(int n, BigInteger[] data) {
    if (n < 0) throw new IllegalArgumentException("N can not be negative");
    else if (n == 0) return BigInteger.ZERO;
    else if (n == 1) return BigInteger.ONE;
    if (data == null) data = new BigInteger[n+1];
    BigInteger result = (data[n-1] == null ? recursiveFibMemoize(n-1, data) : data[n-1]).add(data[n-2] == null ? recursiveFibMemoize(n-2, data) : data[n-2]);
    data[n] = result;
    return data[n];
  }

  /**
   * time: O(n)
   */
  public static BigInteger iterativeFib(int n) {
    if (n < 0) throw new IllegalArgumentException("N can not be negative");
    else if (n == 0) return BigInteger.ZERO;
    else if (n == 1) return BigInteger.ONE;
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;
    for (int i = 2; i <= n; i++) {
      BigInteger result = a.add(b);
      a = b;
      b = result;
    }
    return b;
  }
}