CS 151 Fall 2007 Lab 13

Recursion

The goals for this lab are to get a hands on practice using recursion to solve problems.

1. Open BlueJ either by selecting it from the Dock or navigating to it in the Applications folder and double clicking it.
   
   
2. Mount your network directory/folder so that you can access the lab after you leave Olin 323. Go to the Finder and from the Go menu select Connect to Server.... Type afp://fileserver1 or choose it from the list of selections and select the Personal volume when prompted.
   
   
3. From the Project menu select New Project. Select your computer from the drop down menu. Then scroll down and open the Volumes folder and then the Personal folder inside it. Scroll down the long list of folders until your find yours. Create a project called "Lab13" in your personal network folder.
   
   
4. (Exercise P13.1 from your book) Write a class called Sentence and in it write a recursive method void reverse() that reverses a sentence. For example:
   
   Sentence greeting = new Sentence("Hello!");
greeting.reverse();
System.out.println(greeting);
   
   should print the string "!olleH". Implement reverse as a recursive method that first removes the first character from the sentence, reverses the remainder of the sentence, and changes the sentence to the combination of the two. You can create new Sentence objects within reverse to help. Don't forget to create a constructor for the class and to override its toString() method.

5. (P13.2) Redo the reverse method so that instead of creating new sentence objects, it calls a helper method reverse(int startPos, int endPos) that only reverses the substring of message text from startPos to endPos. Recall that the sentence for which this method is being called is an implicit parameter.

6. (P13.4) Use recursion to implement a method boolean find(String text) that tests whether text is contained within that sentence:
   
   Sentence s = new Sentence("Mississippi");
boolean found = s.find("ssissi"); //returns true
   
   The book suggests first checking to see if the sentence start with the search string. If it matches return true and you're done. Otherwise, try to find the search string in the sentence you get by removing the first character.

7. (P13.5) Use recursion to implement a method int indexOf(String t) that returns the starting position of the first substring in the of the text that matches t. Return -1 if t is not a substring of the sentence. For example,
   
   Sentence s = new Sentence("Mississippi");
int pos = s.indexOf("ssissi"); //returns 2
   
   Hint: This is trickier than preceding problem, because you must keep track of how far the match is from the beginning of the sentence. Make that value a parameter of the recursive helper method you write.

8. Feel free to ask about project related question if you get through all of this.