CS1110       Lab 06. Recursion     Spring 2011 

Name _____________________      NetId __________________________

This lab gives you experience with writing recursive functions. Remember: 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 a String, the base case is a String of length 0, or 0 and 1, usually, but it could be something else. 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.)

  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. Making progress toward termination. In keeping with point 3, the arguments of a recursive call 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 the functions in Rec.java as you can, starting with the first one and going through them one by one. We suggest 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.

Note that the first 8 functions process strings, but the rest of them process integers. Even though you only do the first 3-5 in lab, make sure you do some of the integer ones at home.

In order to "pass" this lab, finish the first 4 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 write one of the functions and test it. If your roommate thinks you are crazy, tell them how much you enjoy doing this. Ask them how they would tile Elaine's kitchen; that will keep them busy for a while and give you time to write a few more recursive functions.

Look at the very end of class Rec.java. The comment before the three test procedures 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 education and enjoyment.