CSC148H lab -- week 5

This document contains the instructions for the week 5 CSC148H lab. To earn your lab mark, you must actively participate in the lab.

This week's lab consists of a sequence of exercises on recursive programming.

Pair programming

As always, you will work as a pair. Remember that in pair programming, the two programmers take turns being the driver and the navigator. The driver types, and the navigator watches for mistakes, thinking ahead.

Getting started

We have provided a startup file that should save you some typing. It contains a class Recursion that includes a main method where a keyboard input object is defined, and "skeletons" for each of the methods required by the exercises below. Here's how to start using it:

1. Decide who is the first driver and the first navigator, and have the first driver log in.
2. Make a new folder called "lab5", and save Recursion.java in this folder. (Since you're alternating roles as driver and navigator, both of you will need to begin by saving this file when it's your turn as driver.)
3. Double-click the DrJava icon, and open Recursion.java.
4. Start the first exercise.

Rules and advice for these exercises

1. Everything must be done recursively.
2. No loops are allowed. That's the same as the first rule, but it needs saying twice.
3. No static variables are allowed. When you need to pass information from one method call to another, use a parameter.
4. You may find it helpful to make recursive helper methods for some or most of these problems. For example, a recursive helper method for printDivisors that has a parameter to keep track of the next possible divisor for i and prints that parameter if it divides into i (and then recurses) might be really handy. For other problems, you may absolutely have to have a helper method. Your helper methods should be private.
5. This may be a rather long lab. Don't worry if you don't finish.
6. Start every exercise by thinking about what the solution should be, not by typing. Recursion is "hard" because you're not used to thinking that way -- because it's different, that is, and not because it's truly difficult. A couple of minutes spent thinking and trying out your solution in your head can help a lot.

For each exercise, we give the method header (the return type and the signature) in the title of the exercise, followed by a description in the body of the exercise. The description includes some of the Javadoc tags you would be expected to write for such a method.

At the end of each exercise, show your TA what you've done.

Exercise 1: void printDivisors(int i)

Print the positive divisors of i, one per line. (3 is a divisor of 9, for example.) Hint: use %.

   @param i the number whose divisors will be printed.
	  

Exercise 2: int countSpaces(String s)

(Don't forget to switch the driver and navigator.)

Return the number of spaces in s.

   @param s the String in which to look for spaces.
   @return the number of spaces in s.
	  

Exercise 3: void printDivisorsSeparated(int i)

Print the positive divisors of i on one line, separated by commas. For example, given 6 it would print

   1, 2, 3, 6

   @param i the number whose divisors will be printed.
      

Exercise 4: String mostSpaces(BufferedReader br)

Return the line that contains the most spaces in br. Stop reading input when you see the line "quit", which should be ignored. You should call countSpaces within your recursive code.

What should be returned if there is no input? You don't have to solve this problem, but you should think about it.

   @param br the input source.
   @return the line in br containing the most spaces.

Exercise 5: List<T> copyWithout(Iterator<T> it, T omittee)

Return a new List that contains all the elements of the original list except those that are the same as omittee -- the thing to be omitted. Instead of an actual list to start with, you're given an iterator through the list as parameter.

This one might be a little too interesting, so we've given you a non-recursive solution to start with, that should help to remind you of the iterator operations and also show you more uses of the new Java 1.5 generics.

   @param it the iterator through the original list.
   @param omittee the object to be omitted from the returned list.
   @return a list containing all the items offered by it except those equal to omittee.