// --------------
// Fibonacci.java
// --------------

final class Fibonacci {
    /**
     * O(phi^n) in space, where phi = (1 + sqrt(5)) / 2
     * O(phi^n) in time
     * Precondition: n >= 0
     */
    public static long recursive (long n) {
        assert n >= 0;
        if (n < 2)
            return n;
        return recursive(n - 1) + recursive(n - 2);}

    /**
     * O(1) in space
     * O(n) in time
     * Precondition: (n >= 0)
     */
    public static long iterative (long n) {
        assert n >= 0;
        if (n < 2)
            return n;
        long x = 0;
        long y = 1;
        for (long i = 1; i != n; ++i) {
            final long t = x + y;
            x = y;
            y = t;}
        return y;}}

final class FibonacciTest {
    public static void main (String[] args) {
        System.out.println("Fibonacc1.java");

        {
        assert Fibonacci.recursive(0) == 0;
        assert Fibonacci.recursive(1) == 1;
        assert Fibonacci.recursive(2) == 1;
        assert Fibonacci.recursive(3) == 2;
        assert Fibonacci.recursive(4) == 3;
        assert Fibonacci.recursive(5) == 5;
        }

        {
        assert Fibonacci.iterative(0) == 0;
        assert Fibonacci.iterative(1) == 1;
        assert Fibonacci.iterative(2) == 1;
        assert Fibonacci.iterative(3) == 2;
        assert Fibonacci.iterative(4) == 3;
        assert Fibonacci.iterative(5) == 5;
        }

        System.out.println("Done.");}}