CSC300 / CSC402: String Concatenation (Recursive) [17/18]

  public static String f (long N) {
    if (N == 0) {
      return "";
    } else {
      String result = "*" + f(N - 1);
      numOps = numOps + result.length();
      return result;
    }
  }

Output

Elapsed count f(            8):               36:      3.600 [     0.000 :        NaN]
Elapsed count f(           16):              136:      3.778 [     0.000 :        NaN]
Elapsed count f(           32):              528:      3.882 [     0.000 :        NaN]
Elapsed count f(           64):            2,080:      3.939 [     0.001 :   Infinity]
Elapsed count f(          128):            8,256:      3.969 [     0.000 :      0.000]
Elapsed count f(          256):           32,896:      3.984 [     0.000 :        NaN]
Elapsed count f(          512):          131,328:      3.992 [     0.000 :        NaN]
Elapsed count f(        1,024):          524,800:      3.996 [     0.001 :   Infinity]
Elapsed count f(        2,048):        2,098,176:      3.998 [     0.003 :      3.000]
Elapsed count f(        4,096):        8,390,656:      3.999 [     0.012 :      4.000]

 Exception in thread "main" java.lang.StackOverflowError
  at java.base/java.lang.StringBuilder.<init>(StringBuilder.java:124)
  at algs14.XCountingRecursion.f(XCountingRecursion.java:18)