01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
package ds1.student.orderofgrowth;
import stdlib.StdOut;
import stdlib.Stopwatch;
public class CountingRecursion {
/* testing an integer function */
public static long f (long N) {
if (N <= 1) {
return 1;
} else {
long result = f(N-1) * N;
steps = steps + 1;
return result;
}
}
// public static String f (long N) {
// if (N == 0) {
// return "";
// } else {
// String result = "*" + f(N - 1);
// steps = steps + result.length();
// return result;
// }
// }
private static long steps;
public static void main (String[] args) {
long MIN = 4L;
long MAX = 5000L; // If too big, you may get a StackOverflowException
Stopwatch sw = new Stopwatch ();
steps = 0;
f(MIN);
double prevCount = steps;
double prevTime = sw.elapsedTime ();
for (long N = MIN*2; N <= MAX; N=N*2) {
sw = new Stopwatch ();
steps = 0;
f(N);
long count = steps;
double time = sw.elapsedTime ();
StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, count, count / prevCount, time, time/prevTime);
//StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f\n", N, count, count / prevCount);
prevCount = count;
prevTime = time;
}
}
}
|
