/*
 * Fibonacci.java
 *
 * Computer Science E-22
 */

/**
 * Recursive and iterative ways to calculate the Nth Fibonacci number
 */
public class Fibonacci {

    /**
     * Use recursion to calculate the Nth Fibonacci number.
     * 
     * Since each call makes two other recursive calls, and those other calls
     * involve recomputing the same Fibonacci numbers, it's not efficient.
     */
    public static long fib(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fib(n - 2) + fib(n - 1);
        }
    }

    /**
     * Use iteration to calculate the Nth Fibonacci number.
     * 
     * This implementation is more efficient, but no longer resembles the
     * definition of the Fibonacci number.
     */
    public static long fibIter(int n) {
        if (n == 0 || n == 1) {
            return n;
        }

        long previous = 0;
        long current = 1;

        for (int i = 2; i <= n; i++) {
            long temp = previous + current;

            previous = current;
            current = temp;
        }

        return current;
    }

    public static void main(String[] args) {
        int maxN = 55;

        for (int n = 0; n <= maxN; n++) {
            long before = System.currentTimeMillis();
            long result = fibIter(n);
            long after = System.currentTimeMillis();
            System.out.printf("F_%d = %d (%d ms)%n", n, result, after - before);
        }

        for (int n = 0; n <= maxN; n++) {
            long before = System.currentTimeMillis();
            long result = fib(n);
            long after = System.currentTimeMillis();
            System.out.printf("F_%d = %d (%d ms)%n", n, result, after - before);
        }
    }
}