CS1110       Lab 06. Recursion     Fall 2008 

Name _____________________       Section time _______________        Section instructor ___________________

In this lab, you will gain experience with writing recursive functions. Remember that creating/understanding a recursive function involves four points.

1. A precise specification of the function. Without this, you cannot write the function.
   
2. Handling the base case properly. The base case involves the "smallest" parameter values, for which the result can be given easily, without the need for recursive calls. For a function that works on the natural numbers 0, 1, 2, ..., the base case is 0, or 0 and 1, usually. (But we give you one function to write for which it is something different.) For a function that works on a String, the base case is a String of length 0, or 0 and 1, usually, but it could be something else.
   
3. Handling the recursive case properly. Solve the original problem in terms of the same problem but on a smaller value. For example, if the function involves a String s, the solution should be describable in terms of the same problem on some substring of s. In writing/understanding a recursive call, understand it in terms of the specification of the function being called.
   
4. In keeping with point 3, in a recursive call, the arguments must be in some measure smaller than the parameters of the method; this is what ensures termination. Each recursive call has "smaller arguments", so that after some point, the base case will be reached.

On your computer, create a new folder. Download file Rec.java from the course website, place it in the new folder, and compile in DrJava. Then, write and test as many of these functions as you can, starting with the first one and going through them one by one. If JUnit testing works for you, create a JUnit testing class and place test cases in it as you go and test as you proceed. This will actually save you time in the end!!!!

If you get stuck, do not waste time! Ask the TA or consultant for help.

In order to "pass" this lab, you should finish the first 5 functions and show them to your TA. However, you will gain more fluency and understanding if you do them all. So, during the week, every once in a while sit down at your computer and write one of the functions. If you roommate thinks your crazy, tell them how much you enjoy doing this. Ask him how he would tile Elaine's kitchen; that will keep them buzy for a while and give you time to write a few more recursive functions.

Look also at the very end of class Rec.java. The comment before procedures test() and test(int) ask you to do some actions to determine how many frames are created by recursive calls on these procedures before "stack overflow" happens. Do this, for you own knowledge and enjoyment.