package class10_2_Fibonacci;

/**
 * Compute fibonacci numbers with O(n) recursion.
 *
 * For fun:
 * (1) See the problem in the book that compares with the exponential running time version.
 * (2) Compare fib and fibD (one uses long, one uses double)
 *    (a) How many bits does each use to store the answer?
 *    (b) Where are the two different?
 *    (c) When would you want to use a long? When would you want to use a double?
 */

public class Fibonacci {
    public static void main(String[] args) {
        new Fibonacci().test();
    }

    private void test() {
        for (int i = 0; i < 200; i++) {
            testFib(i);
            testFibD(i);
        }
    }

    private void testFib(int i) {
        long startNanos = System.nanoTime();
        System.out.println("fib ("+i+")="+fib(i));
        long total = System.nanoTime() - startNanos;
        System.out.println("Took "+total+" ns to run.");
        System.out.flush();
    }

    private void testFibD(int i) {
        long startNanos = System.nanoTime();
        System.out.println("fibD("+i+")="+fibD(i));
        long total = System.nanoTime() - startNanos;
        System.out.println("Took "+total+" ns to run.");
        System.out.flush();
    }

    public long fib(int n) {
       if( n<= 1 ){
           return 1;
       } else {
           return fib(1,1,2,n);
       }
    }

    private long fib(long previous, long current, int i, int goal) {
        if( goal <= 1) { // needed?
            return 1;
        } else if (i==goal) {
            return previous+current;
        } else {
            return fib(current, previous+current, i+1, goal );
        }
    }

    public double fibD(int n) {
       if( n<= 1 ){
           return 1;
       } else {
           return fibD(1,1,2,n);
       }
    }

    private double fibD(double previous, double current, int i, int goal) {
        if( goal <= 1) { // needed?
            return 1;
        } else if (i==goal) {
            return previous+current;
        } else {
            return fibD(current, previous+current, i+1, goal );
        }
    }
}