<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">import java.util.ArrayList;
public class DemoFib {
    public static double goldenRatio=  (1 + Math.sqrt(5))/ 2;                      
    
    /** For 0 &lt;= n &lt; cache.size, fib(n) is cache[n]
      * If fibCached(k) has been called, its result in in cache[k]*/
    public static ArrayList&lt;Integer&gt; cache= new ArrayList&lt;Integer&gt;();
    
    public static int callsOnFib= 0;
    public static int callsOnFibCache= 0;
    
    /** Return fibonacci(n). Pre: n &gt;= 0. 
      * Use the cache. */
    public static int fibCached(int n) {
        callsOnFibCache= callsOnFibCache + 1;
        if (n &lt; 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 &gt;= 0. */
    public static int fib(int n) {
        callsOnFib= callsOnFib+1;
        if (n &lt;= 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 &lt; 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 &lt; 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 &lt;= n; k= k+1) {
            double f= fib(k);
            System.out.println(f/fibPrev);
            fibPrev= f;
        }
    }
}</pre></body></html>