import java.util.ArrayList;
public class DemoFib {
    public static double goldenRatio=  (1 + Math.sqrt(5))/ 2;                      
    
    /** For 0 <= n < cache.size, fib(n) is cache[n]
      * If fibCached(k) has been called, its result in in cache[k]*/
    public static ArrayList<Integer> cache= new ArrayList<Integer>();
    
    public static int callsOnFib= 0;
    public static int callsOnFibCache= 0;
    
    /** Return fibonacci(n). Pre: n >= 0. 
      * Use the cache. */
    public static int fibCached(int n) {
        callsOnFibCache= callsOnFibCache + 1;
        if (n < cache.size()) return cache.get(n);
        if (n == 0) { cache.add(0); return 0;}
        if (n == 1) { cache.add(1); return 1;}
        
        int ans= fibCached(n-2) + fibCached(n-1); 
        cache.add(ans);
        return ans;
    }
    
    /** Return fibonacci(n). Pre: n >= 0. */
    public static int fib(int n) {
        callsOnFib= callsOnFib+1;
        if (n <= 1) return n;
        return fib(n-1) + fib(n-2);
    }
    
    /**Print first n fibonacci numbers */
    public static void printFibs(int n) {
        for (int k= 0; k < n; k= k+1) {
            System.out.println(fib(k));
        }
    }
    
    /**Print first n fibonacci numbers */
    public static void printFibsCache(int n) {
        for (int k= 0; k < n; k= k+1) {
            System.out.println(fib(k));
        }
    }
    
    /** Print fib(n)/fib(n-1) for n in 2..n. */
    public static void printRatios(int n) {
        double fibPrev= 1;
        /** fibPrev = fib(k-1) */
        for (int k= 2; k <= n; k= k+1) {
            double f= fib(k);
            System.out.println(f/fibPrev);
            fibPrev= f;
        }
    }
}