CSC300: Recursive Factorial [15/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 1;
    } else {
      long result = f(N-1) * N;     
      numOps = numOps + 1;
      return result;
    }
  }

Output

Elapsed count f(            8):               7:      2.333 [     0.000 :        NaN]
Elapsed count f(           16):              15:      2.143 [     0.000 :        NaN]
Elapsed count f(           32):              31:      2.067 [     0.000 :        NaN]
Elapsed count f(           64):              63:      2.032 [     0.000 :        NaN]
Elapsed count f(          128):             127:      2.016 [     0.000 :        NaN]
Elapsed count f(          256):             255:      2.008 [     0.000 :        NaN]
Elapsed count f(          512):             511:      2.004 [     0.000 :        NaN]
Elapsed count f(        1,024):           1,023:      2.002 [     0.000 :        NaN]
Elapsed count f(        2,048):           2,047:      2.001 [     0.000 :        NaN]
Elapsed count f(        4,096):           4,095:      2.000 [     0.000 :        NaN]
Elapsed count f(        8,192):           8,191:      2.000 [     0.000 :        NaN]

This is linear: ~ N