/******************************************************************************
 * Name:
 * Login:
 * Precept:
 * 
 * Computes and prints the first N Fibonacci numbers.
 *
 * WARNING:  This program is spectacularly inefficient and is meant
 *           to illustrate a performance bug, e.g., set N = 45.
 *
 *  Compilation:  javac-introcs Fibonacci.java
 *  Execution:    java-introcs Fibonacci N
 *
 * % java-introcs Fibonacci 7
 *   1: 1
 *   2: 1
 *   3: 2
 *   4: 3
 *   5: 5
 *   6: 8
 *   7: 13
 *
 *   Remarks
 *   -------
 *    - The 93rd Fibonacci number would overflow a long, but this
 *      will take so long to compute with this function that we
 *      don't bother to check for overflow.
 * 
 *                                                   From 2.3 Recursion
 ******************************************************************************/

public class Fibonacci {
    public static long fib(int n) {
        if (n <= 1) return n;
        else return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        // print results                                                     
        System.out.println(fib(N));

        // print each loop
        for (int i = 1; i <= N; i++)
            StdOut.println(i + ": " + fib(i));
    }

}