1/*2 * Fibonacci.java3 *4 * Computer Science S-225 */6 7/**8 * Recursive and iterative ways to calculate the Nth Fibonacci number9 */10public class Fibonacci {11 12 /**13 * Use recursion to calculate the Nth Fibonacci number.14 * 15 * Since each call makes two other recursive calls, and those other calls16 * involve recomputing the same Fibonacci numbers, it's not efficient.17 */18 public static long fib(int n) {19 if (n == 0) {20 return 0;21 } else if (n == 1) {22 return 1;23 } else {24 return fib(n - 2) + fib(n - 1);25 }26 }27 28 /**29 * Use iteration to calculate the Nth Fibonacci number.30 * 31 * This implementation is more efficient, but no longer resembles the32 * definition of the Fibonacci number.33 */34 public static long fibIter(int n) {35 if (n == 0 || n == 1) {36 return n;37 }38 39 long previous = 0;40 long current = 1;41 42 for (int i = 2; i <= n; i++) {43 long temp = previous + current;44 45 previous = current;46 current = temp;47 }48 49 return current;50 }51 52 public static void main(String[] args) {53 int maxN = 55;54 55 for (int n = 0; n <= maxN; n++) {56 long before = System.currentTimeMillis();57 long result = fibIter(n);58 long after = System.currentTimeMillis();59 System.out.printf("F_%d = %d (%d ms)%n", n, result, after - before);60 }61 62 for (int n = 0; n <= maxN; n++) {63 long before = System.currentTimeMillis();64 long result = fib(n);65 long after = System.currentTimeMillis();66 System.out.printf("F_%d = %d (%d ms)%n", n, result, after - before);67 }68 }69}