CSC300: Recursive Fibonacci (Terrible Version) [16/19]

We will cover recursion later in the course, so you don't need to understand this slide for the Midterm.

  public static long f (long N) {
    if (N <= 1) {
      return N;
    } else {
      long result = f(N-1) + f(N-2);      
      numOps = numOps + 1;
      return result;
    }
  }

Output

Elapsed count f(            8):               33:      8.250 [     0.000 :        NaN]
Elapsed count f(           16):            1,596:     48.364 [     0.000 :        NaN]
Elapsed count f(           32):        3,524,577:   2208.382 [     0.011 :   Infinity]
Elapsed count f(           64) aborted execution after a thousand hours or so
Elapsed count f(          128) aborted execution after a thousand hours or so
Elapsed count f(          256) aborted execution after a thousand hours or so
Elapsed count f(          512) aborted execution after a thousand hours or so
Elapsed count f(        1,024) aborted execution after a thousand hours or so
Elapsed count f(        2,048) aborted execution after a thousand hours or so
Elapsed count f(        4,096) aborted execution after a thousand hours or so
Elapsed count f(        8,192) aborted execution after a thousand hours or so

This is exponential: approximately 2^N

More accurately: (1.6)^N, where 1.6 = (1+sqrt(5))/2