CSCI 235 Lab 6: Introducing recursion

You will be working with your partner on one of your accounts.

This lab introduces the idea of writing recursive methods.

1. Setup

Move to your directory for this class. Clone the provided repository to get the starting point for this lab.

That makes a new directory lab6, where you will be working today.

2. Initial examples

Open the file Examples.java in Emacs.

2.1 probA() and countDown()

Compile and run Examples.java. It includes the method probA() from your assignment

In its initial form, the program calls this method with the arguments 0, 3, and 4.

Now look at the method countDown(), which is almost the same. The key differences are that this method prints something at the beginning and end of every call, and the additional parameter indent is used to help you see the way that the lines printed are related. Go to main() and comment out the call to showProbA() and uncomment showCountDown(). When you (compile and) run it now, what you’ll see for the call with 3 looks like this:

This shows how the activation of countDown() for 3 calls the one for 2, and so on until the call for 0. We often describe uutput that shows the intermediate steps in a computation as tracing the execution.

2.2 probC()

A recursive method can have more than one base case, as shown in probC(). You can uncomment the call to showProbC() to see what it prints.

The method probCx() does the same thing, but prints at the beginning and end of each call (using an extra parameter to indent nicely). Uncomment the call to showProbCx() to see the steps along the way.

2.3 probCy()

This is a slight rewrite of the previous method so that the tracing can turned on or off by providing the indentBy parameter. You can see how this works by selectively uncommenting the calls to showProbCy() in main(). This technique will be useful in the next section.

3. Writing your own

Now it is your turn. Open the file Curses.java. Your job will be to write a method that recursively computes the greatest common divisor of two positive integers.

Before you work on that, notice that I have set up the main method so that you can run the program with one or two arguments. The first argument turns into the parameter n. The second parameter—if supplied—becomes the prefix for indentation. So you should (eventually) be able to run your program with

to see just the result, or with

to see it with a trace of calls.

I have also provided you with a a file Blessings.class to help you check your answers. Your program should produce the same output as that program.

3.1 A tracing version

It is easier to work on something when you can see how it works. So start by filling in the code you need in the tracing version of the method, traceGcd().

Expressed recursively, Euclid’s algorithm for computing the greatest common divisor of m and n is based on the following observations:

• If m and n are the same, either of them is clearly their gcd.
• If they are not equal, their gcd is the same as the gcd of the smaller of the two and their difference (larger minus smaller).

Complete traceGcd() and verify that it works correctly (both tracing and not tracing).

3.2 Cleaning it up

After you have that working, copy the code into the non-tracing version gcd(), getting rid of the extra stuff. Don’t forget to change any recursive calls.

If the second command-line argument is no, the program Curses will call the non-tracing version. Make sure that it works.

4. Turn in

Commit your changes to Mercurial.

Create a script file to show your program compiling and running. Run Curses so that it calls the tracing version of your method for several different values of n, with and without a tracing prefix. Then run Curses again for the same set of values, but with a second argument of no so that it calls the non-tracing version of your method.

Turn in Curses.java and your script putput as lab6. Do not turn in a printed copy.

Copy the repository to the other partner’s account.