// This program allows you to time recursive and iterative factorial
// methods. Each of these methods is so fast, that the computer's
// clock is not sensitive enough to measure its speed. Therefore,
// to measure the running time of iFactorial() or rFactorial(), this
// program calls each method many times in succession (the
// LOOP_TIMES constant controls how many times), then divides the
// running time by LOOP_TIMES for display.
import Keyboard;
public class TestRecursion
{
// rFactorial: Returns the factorial of the number.
// (Recursive version)
// Note: The number must be positive.
static long rFactorial(long number)
{
if (number == 0)
{
return 1;
}
else
{
return number * rFactorial(number - 1);
}
}
// iFactorial: Returns the factorial of the number.
// (Iterative version)
// Note: The number must be positive.
static long iFactorial(long number)
{
long product = 1;
for (long i = 1; i <= number; i++)
{
product = product * i;
}
return product;
}
// This value controls how many times the program calls the factorial method
// per test
static final long LOOP_TIMES = 1000000;
// recursiveTest: Returns how long it takes to call rFactorial(number)
// in milliseconds
static double recursiveTest(long number)
{
long recursiveStartTime = System.currentTimeMillis();
for (int i = 0; i < LOOP_TIMES; i++)
{
long factorial = rFactorial(number);
}
return (double) (System.currentTimeMillis() - recursiveStartTime)
/ LOOP_TIMES;
}
// iterativeTest: Returns how long it takes to call iFactorial(number)
// in milliseconds
static double iterativeTest(long number)
{
long iterativeStartTime = System.currentTimeMillis();
for (int i = 0; i < LOOP_TIMES; i++)
{
long factorial = iFactorial(number);
}
return (double) (System.currentTimeMillis() - iterativeStartTime)
/ LOOP_TIMES;
}
public static void main(String[] args)
throws java.io.IOException
{
// Run methods quickly, so the just-in-time (JIT) compiler has
// chance to compile them...
double value = recursiveTest(2);
value = iterativeTest(2);
while (true)
{
System.out.println();
long number = Keyboard.readLong("Number to find factorial of (-1 to quit): ",
-1, 100);
if (number == -1) break;
System.out.println();
System.out.println("Milliseconds per factorial calculation");
double recursiveTime = recursiveTest(number);
double iterativeTime = iterativeTest(number);
System.out.println(" Recursive: " + recursiveTime);
System.out.println(" Iterative: " + iterativeTime);
System.out.println("Recursion to iterative ratio: "
+ recursiveTime / iterativeTime);
}
}
} |