This lab will give you a chance to work with a powerful concept known as recursion. This is a deep and profound topic that pops up in mathematics, science, philosophy, and even the arts. In programming applications, recursion appears in the guise of methods that invoke themselves.
Some of your tasks will involve downloading and running ready-to-go applications that illustrate essential features of all recursive methods. Most of these programs are available on the Booksite for your text.
The principle of recursion is introduced in Section 2.3 of your text. This lab will feature several of the demo applications listed there.
To complete this project, follow the steps listed below:
For a more detailed version of this procedure, see Step 6 in Lab 08.
When you think you understand all that you see, Build the project to create the distribution JAR file Lab09.jar.
java -cp dist/Lab09.jar:../Booksite1.jar Factorial
java -cp dist/Lab09.jar:../Booksite1.jar Harmonic
As you learned last week in Lab 08
(see step 9), these commands have to include Booksite1.jar as
well as the project distribution JAR file Lab09.jar in the
runtime classpath. Also note the absence of command-line
arguments, since both of these programs will prompt you to enter
the arguments from the keyboard.
Your only remaining task in this section is to confirm for yourself that these programs actually produce correct results, and to make sure that you understand just how the recursive methods in each program actually work. Then demonstrate both of these programs to your lab instructor. But don't worry, it gets harder after this...
As soon as you written and tested both methods, show your source code for PowersOfTwo to your lab instructor.
Euclid.java uses Euclid's algorithm to compute the greatest common divisor (GCD) of two integers. It is a clever but subtle method, which may not be all that transparent when you first look at it. You can find a decent explanation in your text (see pp. 259-260), or in Section 2.3 of the Booksite. And you should certainly feel free to embarrass your lab instructor at this point by asking deep and penetrating questions about this algorithm. But in any event you should note that Euclid's algorithm is naturally recursive, which shows that the basic idea of recursion is as old as it is powerful.
Of course there are other algorithms for finding the GCD of two integers. One straightforward approach, which you may well find easier to understand on a first reading, can be implemented as follows:
public static int gcd (int p, int q) {
int gcd = 1;
int n = 1;
while (n <= p && n <= q) {
if (p % n == 0 && q % n == 0) {
gcd = n;
}
n++;
}
return gcd;
}
Now it is sometimes true that the simplest-minded solution to
a problem is also the most efficient, but unfortunately that does
not hold in every case. To see whether we really need to bother
with Euclid's clever method in this age of fast computers,
create a new Empty Java File named MyEuclid.java
in the default
directory for Lab09 and start to fill it in by copying
the entire contents of Euclid.java. Then rename
the method gcd() (the recursive version) to gcd1().
(Leave the iterative version gcd2() unchanged.)
Next add the source code for the method listed above to MyEuclid.java, and rename this version to gcd3(). Then modify the main() method so that it invokes all three methods in succession for the same pair of command-line arguments p and q.
Build your Lab09 project, then use the terminal window to run MyEuclid. Enter various combinations of p and q and confirm that all three GCD methods produce identical results for each combination. If that is not the case, something is dreadfully wrong. If you cannot quickly detect an error in your source code, consult with your lab instructor before proceeding further.
When you are confident that all the methods are working correctly, you are ready to compare their time performance. Now you may already have noticed that a single call to each method takes very little time, in fact far too little to measure with a stopwatch. But you can actually make decent comparisons of each of these methods if you make them perform the same action many times. And you can do just that if you replace each of the current method calls in main() by something like the following code:
int T = 1000; // Number of "trials"
int d = 1; // d = gcd(p,q)
long t0 = System.currentTimeMillis(); // Start time (ms)
for (int t = 0; t < T; t++) // Call gcd(p,q) T times
d = gcd(p,q);
long t1 = System.currentTimeMillis(); // End time (ms)
System.out.println ("gcd(" + p + ", " + q + ") = " + d
+ " (" + (t1 - t0) + " ms)");
Note that this code uses a method named System.currentTimeMillis(). This is a standard Java library method that returns the current value of the system clock. More precisely, it returns the number of milliseconds that have elapsed since midnight (GMT) on January 1, 1970. This code measures the time required to perform the specified loop by computing the difference between the start and end times. Of course the proper quantity to measure here should be the running time for a single call to each method, which would be just (t1 - t0)/T. But the code above is sufficient to compare the relative time performance of these methods.
So use this sample code to revise main() so that it compares the running times for each method for an identical number of repetitions or trials T. While you are at it, also revise main() so that it accepts the value of T as a third command-line argument, following p and q.
Build Lab09 yet again, then run MyEuclid with large values of p and q, but initially with a small or moderate number of trials T. Then start increasing T, say by a factor of 10 each time. It should not be long before you can decide for yourself if the straightforward algorithm can hold its own against good old Euclid. You also want to compare the relative performance of the explicitly recursive method gcd1() with the iterative implementation of Euclid's algorithm, namely gcd2(). Whenever you are ready to stand by your conclusions, show your results to your lab intructor.
Now Build the project again and run Htree from the terminal window using each of the values you considered above. Then get bold and try some larger values.
Just to complete the formalities, show your Htree results to your lab instructor.
When your project is complete and working correctly, demonstrate it to your lab instructor. Then, before you exit NetBeans, clean your Lab09 project. Finally, before you logout, switch back to your terminal and set your default directory back to csci/273.002/labs. Then create a JAR file of your Lab09 project folder, using the command
jar cf Lab09Project.jar Lab08Please leave both your Lab09 project folder and Lab09Project.jar in your csci/273.002/labs directory for the remainder of the semester.