Lab 6: Recursive methods

The goal of this lab is to practice writing and working with recursive methods. The methods you write today will not contain any loops.

1. Setup

Move into the directory for this class; clone the repository to get the starting point for this lab.

hg clone /cslab/class/csci235/labs/lab6

The new directory has a file with the stubs for eight methods that you will to write, as well as a simple main method to test these methods out using information from the args array. In each section below, you will be instructed to fill in the body for one of these methods; you also should uncomment the code in the main method that tests it.

Notice that some of the test calls in main() require just one argument, while a few require two. In particular, note that the call to contains() passes just the first character from the second command-line argument.

You should fill in the heading now, so that you don't forget. You might want to commit after you've done that. In fact, you'll probably want to commit after each of the steps.

For many of these problems, it may be helpful to think of a string as being either

• the empty string, or
• a character followed by a string.

2. Computing a String's length

Write a recursive method that will compute a String's length. You may use only the substring() and isEmpty() methods on class String.

3. Computing containment

Write a recursive method that will determine if a string contains a particular character. (Clearly, using isIndex() would be cheating.)

4. Computing if two Strings are equal

Write a recursive method that will compute whether or not two Strings are equal to each other (i.e., contain the same characters in the same order). You may use only length(), isEmpty(), charAt(), and substring().

5. Computing palindromes recursively

You've already programmed at least one algorithm for determining whether or not a String is a palindrome. Now you need to figure out a recursive method to do it. Work out the algorithm on your own, but here's a recursive definition of a palindrome to get you started:

A palindrome is

• an empty string,
• a string with exactly one character,
• or the string that results from prepending and appending the same character to a palindrome.

(Remember, "prepend" means "concatenate to the front" and "append" means "concatenate to the back.")

Write the isPalindrome() method and test. (Don't worry about mixed case or ignoring non-letters.)

6. Reversing strings

Write a method that will reverse a String. First write out a recursive definition of what the reverse of String is; then transform that definition into a recursive algorithm for computing the reverse of a String.

7. Computing prefixes

Write a recursive version of the method startsWith.

8. Computing semordnilap

Write a recursive method that will determine if two Strings are semordnilap—i.e., whether one is the reverse of the other. You may not use your reverse() method.

9. Turn in

Create a script file to show your program compiling and running. Run the program using a variety of (pairs of) words.

Turn in your source and script as lab6.

Do not turn in a printed copy.

(As usual, you probably want to copy the repository to your own account.)