// Week 12 – Fibonacci numbers: naive recursion (exponential), memoization and iteration (linear)
// Run: java Fibonacci.java
import java.util.HashMap;

public class Fibonacci {
    static long calls = 0;

    // Naive recursion – tree recursion, O(2^n) calls
    static long fib(int n) {
        calls++;
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

    // Memoization: the values already computed are stored (hash table!) – O(n)
    static HashMap<Integer, Long> memo = new HashMap<>();

    static long fibMemo(int n) {
        calls++;
        if (n < 2) return n;
        Long cached = memo.get(n);
        if (cached != null) return cached;
        long r = fibMemo(n - 1) + fibMemo(n - 2);
        memo.put(n, r);
        return r;
    }

    // Iteration – O(n) time, O(1) space
    static long fibIter(int n) {
        long a = 0, b = 1;
        for (int i = 0; i < n; i++) {
            long t = a + b;
            a = b;
            b = t;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(" n   fib(n)        naive calls    memo calls     time (naive)");
        for (int n : new int[] { 5, 10, 20, 30, 40 }) {
            calls = 0;
            long t0 = System.nanoTime();
            long r = fib(n);
            long t = System.nanoTime() - t0;
            long naive = calls;
            calls = 0;
            memo.clear();
            fibMemo(n);
            System.out.printf("%2d %10d %15d %13d %10.1f ms%n", n, r, naive, calls, t / 1e6);
        }
        System.out.println("fibIter(90) = " + fibIter(90));
    }
}