Fibonacci2.java


Below is the syntax highlighted version of Fibonacci2.java from §2.3 Recursion.


/******************************************************************************
 *  Compilation:  javac Fibonacci2.java
 *  Execution:    java Fibonacci2 n
 *  
 *  Computes and prints the first n Fibonacci numbers using the
 *  following recurrence:
 *
 *         f(1) = f(2) = 1
 *         f(n) = f((n+1)/2)^2 + f((n-1)/2)^2   if n is odd
 *         f(n) = f(n/2 + 1)^2 - f(n/2 - 1)^2   if n is even
 *
 *   % java Fibonacci2 7
 *   0
 *   1
 *   1
 *   2
 *   3
 *   5
 *   8
 *   13
 *
 *   Remarks
 *   -------
 *    - The 93rd Fibonacci number would overflow a long
 *
 ******************************************************************************/

public class Fibonacci2 {

    public static long fib(int n) {
        // base case
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 1;
        if (n >= 93) throw new RuntimeException("Input out of bounds");

        // n is odd
        if (n % 2 != 0) {
            long a = fib((n+1)/2);
            long b = fib((n-1)/2);
            return a*a + b*b;
        }

        // n is even
        long a = fib(n/2 + 1);
        long b = fib(n/2 - 1);
        return a*a - b*b;
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        for (int i = 0; i <= n; i++)
            StdOut.println(i + ": " + fib(i));

        long sum = 0;
        for (int i = 0; i <= n; i++)
            sum += fib(i);
        StdOut.println(sum);
    }

}



Copyright © 2000–2017, Robert Sedgewick and Kevin Wayne.
Last updated: Fri Oct 20 14:12:12 EDT 2017.