Overview

We have reviewed methods and method calls, but there is one particular form we have not yet addressed: recursive methods. In many important ways, there is nothing special about recursion -- it is still calling on a method to produce some result. However, solving problems recursively and understanding how those solutions work can take some practice, so that is what we'll do in this first project.

Working in the lab

I describe here how to use the computers in the lab (SMudd 014) to do your work. Note that all of the college's public, Windows-based computers are configured identically, and so these instructions apply to them. If you want to work on a different machine, read the instructions for logging in from a private computer (both on- and off-campus).

To get started, follow these steps:

1. Login to Windows on one of the lab computers using your college username and password.

2. Start the program NX by selecting Start -> Course Related -> Amherst NX Client.

3. Select either remus or romulus as the machine to which you want to connect. Both are Linux servers, identially configured, so the choice of machine does not matter. Enter your college usename and password when NX prompts you for it, and press Enter to connect.

4. You should, after a few moments, get a window with a complete graphical interface. When you do, move the mouse pointer onto the desktop space within this graphical interface and click-and-hold the right mouse button. A drop-down menu will appear, from which you should select Terminal.

5. A window should appear with a command-line, waiting for you to type commands. Try typing ls and pressing Enter to see a listing of the files and subdirectories within your home directory on remus/romulus.

If you have gotten this far, you are logged into one of the servers on which we will do all of our work. You can move onto the next section.

The Project 1 code

Now that you are logged in, you need to get started on Project 1 itself. Follow these steps to get started:

1. Project 1 requires that you modify a single method inside of code that I've already written. To get a copy of that code from my home directory, use the following command, being certain not to forget the trailing period which is, yes, preceeded by a space:

   cp -r ~sfkaplan/public/cs12/project-1 .

2. You've just copied an entire subdirectory; now change into it:

   cd project-1

3. Take a look at the files:

   ls -l

4. There are a lot of files in that subdirectory, but only one Java source code file, named MyTowers.java, for you to edit. So, open the file in our text-editor-of-choice:

   emacs MyTowers.java &

   First, note the use of the ampersand at the end of that command. Its presence tells the server that you want to run emacs in the background, thus allowing you to enter another command into the terminal window even while emacs continues running.

   Second, if you are unfamiliar with emacs, then type ctrl-h (that is, hold down the ctrl key like you would a shift key, and then type h), followed by the letter t. For short, this command in emacs would be written "C-h t. You will find that this emacs command brings you to a built-in tutorial that will get you started on using it.

5. Now that you are looking at the MyTowers code, scroll down to the bottom. The ultimate method in this file is named moveRings. (Note that you can ignore the other methods above this one -- they're already written and working properly.) Within that method, you'll see a comment in the code that reads *** START HERE ***. Read the large comment below that marker, but don't write any code yet. That step will come soon.

Compiling and running

Before you make any changes to the code, note that it comes in a form that compiles and runs. In its initial state, it doesn't solve the Towers of Hanoi puzzle at all, but it does set up the puzzle. We'll use this opportunity, before you enter any (possibly buggy) code, to see how to compile and run this program.

Compiling: To compile this program, you need only compile the MyTowers code, like so:

javac MyTowers.java

In this case, no compilation errors should appear. Later, though, as you write new code, the compiler may provide some error listings. Note that the compiler tries to provide meaningful and accurate error messages, but sometimes it fails to do so. Specifically, it may point to code that comes slightly after the real error (where the erroneous code simply confused the compiler), or it may provide an utterly obtuse error message. In either case, if you don't understand where the error is, then ask me for help.

Running: Assuming that there were no errors during compilation, you can now run the program. Note that this program accepts command-line arguments -- that is, extra values provided along with the command that makes the program run that tells the program what to do. In particular, this program takes two command-line arguments:

1. Number of rings: The number of rings to initially stack on one post and, of course, then move. Enter a positive integer here.

2. User interface type: This program can display its results textually (using so-called ASCII art to draw the rings and posts) or graphically (by creating a window and drawing rectangles to represent the rings and posts). The latter is easier to view and correlate with the real-world game; the latter provides you a record of the state of the game at every move. The textual version also progresses more rapidly, since it assumes that you can scroll back and review the progression of the game later. Enter either Text or Graphic here.

So, to actually run the program with 5 rings, displaying the results graphically, use this command:

java MyTowers 5 Graphic

Note that if you choose to use the textual interface, the results my fly by too quickly, and the results may be so lengthy that the terminal window does not let you scroll back far enough. In this case, use output redirection to have the textual output dumped into a file instead of shown the screen:

java MyTowers 7 Text > results.txt

You can then open this file in emacs to view its entirety at your leisure.

Your assignment

Remember that long comment, within the moveRings method of MyTowers.java, that began with *** START HERE ***? Well, start there. Read the comment and do what it says. Specifically, write the moveRings method such that it will move the requested number of rings from the source post to the destination post. Note that some other part of my code will call on this method, asking it to move the entire stack of rings from the left-most (0^th) post to the right-most (2^nd) post, thus starting the progression of moves. If you write this method correctly, you should be able to run it and see the results.

Note that if your code causes an illegal move, then the program will crash. If you have difficulty interpreting the crash results and debugging, talk to me.

Submitting your work

All work will be submitted electronically. Specifically, from within your project-1 subdirectory, use the following command to submit you work when you are done:

cs12-submit project-1 MyTowers.java

Note that if you use this command more than once, I will still receive every version of what you've submitted. So, don't worry about clobbering an old submission, and feel free to re-submit if you improve some part of your solution.

Note that the first use of this submission program always reveals a bug or two. I cannot debug it fully without your help, since it may work for me (as the recipient of the files), but not for you (as someone using the program from a different account who has different permissions on the system). So, if you have problems with your submission, email me immediately and describe the problem in detail. I will try to fix it quickly.