import java.util.*;

class Foo {
  
  public static int gcd(int x, int y) {
    // gcd(x,y) == gcd(y,x%y)
    if (y == 0)
      return x;
    else
      return gcd(y, x%y);
    /*
    while (y > 0) {
      int r = x%y;
      x = y;
      y = r;
    }
    return x;
    */
  }

  public static int iterativeFib(int n) {
    // iterative
    int prev = 1;
    int prevPrev = 1;
    int current = 1;
    for (int i=1; i<n; i++) {
      current = prev + prevPrev;
      prevPrev = prev;
      prev = current;
    }
    return current;
  }
  
  // 1, 1, 2, 3, 5, 8, 13, 21, 34,...
  public static int fib(int n) {
    if (n < 2)
      return 1;
    else
      return fib(n-1) + fib(n-2);
  }
  
  private static HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();

  // 1, 1, 2, 3, 5, 8, 13, 21, 34,...
  public static int memoizedFib(int n) {
    int result;
    if (map.containsKey(n))
      // memoized case
      result = map.get(n);
    else if (n < 2)
      // base case
      result = 1;
    else
      // recursive
      result = memoizedFib(n-1) + memoizedFib(n-2);
    map.put(n, result);
    return result;
  }
  
  public static void main(String[] args) {
    System.out.println(gcd(14, 10));

    int lo=35;
    int hi=45;
    System.out.println("iterativeFib: ");
    for (int n=lo; n<=hi; n++)
      System.out.println(n + ": " + iterativeFib(n));
    System.out.println("memoizedFib: ");
    for (int n=lo; n<=hi; n++)
      System.out.println(n + ": " + memoizedFib(n));
  }
}