001package algs14; 002import stdlib.*; 003public class XCountingRecursion { 004 /* testing an integer function */ 005 public static long f (long N) { 006 if (N <= 1) { 007 return 1; 008 } else { 009 long result = f(N-1) * N; 010 numOps = numOps + 1; 011 return result; 012 } 013 } 014// public static String f (long N) { 015// if (N == 0) { 016// return ""; 017// } else { 018// String result = "*" + f(N - 1); 019// numOps = numOps + result.length(); 020// return result; 021// } 022// } 023 private static long numOps; 024 public static void main (String[] args) { 025 long MIN = 4L; 026 long MAX = 5000L; // If too big, you may get a StackOverflowException 027 Stopwatch sw = new Stopwatch (); 028 numOps = 0; 029 f(MIN); 030 double prevCount = numOps; 031 double prevTime = sw.elapsedTime (); 032 for (long N = MIN*2; N <= MAX; N=N*2) { 033 sw = new Stopwatch (); 034 numOps = 0; 035 f(N); 036 long count = numOps; 037 double time = sw.elapsedTime (); 038 StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, count, count / prevCount, time, time/prevTime); 039 //StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f\n", N, count, count / prevCount); 040 prevCount = count; 041 prevTime = time; 042 } 043 } 044}