# 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 fib2(int n) {
int f = 0, g = 1;
for (int i = 1; i <= n; i++) {
f = f + g;
g = f - g;
}
return f;
}

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) + " " + fib2(i));
}
}

}

```