Lab 09

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:

1. Login to your home directory and launch a terminal window. Use the cd command to change your default directory to csci/273.002/labs. Keep this window open for future reference.
2. Launch the NetBeans IDE and raise the New Project dialog. Define the project to be a Java Application named Lab09. Make sure that the project folder will be created within your csci/273.002/labs folder. As in your previous labs, you should also uncheck the Create Main Class checkbox before you click Finish.
3. Several of the applications you will be downloading into Lab09 are in fact clients of library classes that you gathered and archived into the JAR file Booksite1.jar as part of Lab 08 last week. So your next task is to make all those library classes available to your Lab09 project. But hopefully Booksite1.jar should still be lying around in your csci/273.002/labs folder. If not, just download the equivalent archive Booksite1.jar into csci/273.002/labs now. In either case, you will next need to repeat the following procedure in the NetBeans IDE:
   • Select the Projects view, right-click on the Lab09 project name, and select the Properties option in the popup menu to raise the property sheet dialog.
   • In the left-hand panel labeled Categories, select Libraries.
   • In the right-hand panel of the resulting dialog, click Add JAR/Folder.
   • In the resulting subdialog, find and select Booksite1.jar. Then click Open to add it to your project classpath.

   For a more detailed version of this procedure, see Step 6 in Lab 08.

4. The first two recursive methods discussed in your text are actually posted on the Booksite, although the only links to them appear to be in the notes for Section 2.3. But for the purposes of this lab, you can instead download the similar home-grown demos Factorial.java and Harmonic.java into the default package for Lab09. As you will see, these versions include both recursive and iterative (loop-based) algorithms for finding factorials and harmonic numbers respectively. They also happen to demonstrate the convenience of using keyboard input instead of command-line arguments in some situations.
5. As soon as you have downloaded both sources into your Lab09 project, open each file in the NetBeans editor and read through all the code (don't worry, these are both very short files). In each case, you will find two methods that produce the same results for the same input.

   When you think you understand all that you see, Build the project to create the distribution JAR file Lab09.jar.

6. Now return to your terminal window, and enter the command cd Lab09 to set your default directory to be the Lab09 project folder. You are now ready to run Factorial and Harmonic using the following terminal commands:

   
       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...

7. OK, so now it is your turn. Your next task is to create a new Java main class named PowersOfTwo and add it to the default package for Lab09. This class should be similar in structure to Factorial.java and Harmonic.java, in that it must contain one recursive and one iterative method, say pow2a() and pow2b(), each of which accepts a single nonnegative integer argument n and returns 2ⁿ. It also would be convenient for its main() method to read values of n from standard (keyboard) input, just as Factorial and Harmonic do. So it actually is reasonable, and certainly acceptable, if you just copy one of these programs and then do a massive rewrite.

   As soon as you written and tested both methods, show your source code for PowersOfTwo to your lab instructor.

8. To start your next task, return to the Booksite and find the demo program Euclid.java (Program 2.3.1 in your text). Download the plain-text version of this file into the default directory for Lab09, and then open it in the NetBeans editor.

   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.

9. Your final (short!) exercise in this lab is included mainly to give you a preview of coming attractions. Return yet another time to the Booksite and find the demo program Htree.java (Program 2.3.4 in your text). This is your first application dealing with recursive graphics, which will be the theme of your next lab session. Download the plain-text version of this file into the default directory for Lab09, and then open it in the NetBeans editor. Study the code for a while and see if you can anticipate the figure it will draw when its single command-line argument n is the value 1. Then do the same when n is 2, and finally try the value 3.

   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 Lab08