Question

The Fibonacci series of numbers is a favorite of mathematicians, and goes as follows: 1, 1, 2, 3, 5, 8, 13, 21, . . . That is, the first two numbers are 1, and every subsequent number is the sum of the previous two. The mathematical definition as a recursive function is the following.

∀n = 0, 1, 2, . . .

F(n) = { 1 if n <=1

F(n-1) + F(n-2) if n > 1

The closed form of such function is in O(φ n ), where φ is a number called the golden ratio.

1. Coding: Write a Java class Fibonacci that has the following static methods.

(a) (20 points) A recursive method that returns F(n).

(b) (20 points) A non-recursive method that returns F(n).

(c) (10 points) A main method to obtain from the user the index n, and call the methods above one after the other. For each of the method calls, measure and display the running time using the following snippet of code.

...

// store the time now

long startTime = System.nanoTime();

// your method call here

...

// display the time elapsed

System.out.println("t = " +

(System.nanoTime() - startTime) + " nanosecs.");

2. Experiments: (10 points) Measure running times for different values of n and fill a table like the following. (You may need to adjust n to smaller values if it takes too long or your stack overflows, 0 points if you do not have at least 5 columns of measurements.)

n | 0 | 1 | 2 | 4 | 6 | 8 | 16

recursive |   | | | |   | |

non-recursive | | | | | | |

3. Analysis: For your recursive method:

(a) (10 points) What is the worst-case big-O running time with respect to n? (Explain how you computed the running time, 0 points if you do not say what is the basic operation counted and what counting rules you used.)

(b) (10 points) Are your measurements consistent with this big-O running time? (Explain using your measurements, 0 points if you do not say something like "looking at row recursive, when n is doubled the running time is xxx".)

For your non-recursive method:

(c) (10 points) What is the worst-case big-O running time with respect to n? (Explain how you computed the running time, 0 points if you do not say what is the basic operation counted and what counting rules you used.)

(d) 10 points Are your measurements consistent with this big-O running time? (Explain using your measurements, 0 points if you do not say something like "looking at row non-recursive, when n is doubled the running time is xxx".)

Answer 1

• Coding:

1. Recursive method:

static int fibRec(int n) {
       if (n <= 1) {
           return 1;
       } else {
           return fibRec(n - 1) + fibRec(n - 2);
       }
   }

2. Iterative Method:

static int fibItr(int n) {
       int a, b, c = 1;
       a = 1;
       b = 1;
       for (int i = 2; i <= n; i++) {
           c = a + b;
           a = b;
           b = c;
       }
       return c;
   }

3. Main Method:

private static Scanner s;

   public static void main(String[] args) throws Throwable {
       s = new Scanner(System.in);
       System.out.println("Please input a number:");
       int number = s.nextInt();
       long startTime = System.nanoTime();
       System.out.println(fibRec(number));
       System.out.println("t for Recursive Approach = " + (System.nanoTime() - startTime) + " nanosecs.");
       startTime = System.nanoTime();
       System.out.println(fibItr(number));
       System.out.println("t for Iterative Approach = " + (System.nanoTime() - startTime) + " nanosecs.");
   }

• Experiments

n        | 0          | 1     | 2        | 4        | 6      | 8         | 16

recursive | 139200 | 141600 | 166000 | 147401 | 132800 | 461800 | 517001

non-recur | 26200 | 28300   | 30400 | 29000 | 26001 | 30100   | 28001