Lab 5: Recursive methods

The goal of this lab is to practice writing and working with recursive methods.

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/lab5

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 which tests it.

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.

2. 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. Figure 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.

3. 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.

4. Computing prefixes

Write a recursive version of a method startsWith.

5. Computing containment

Write a recursive method which will determine if a string contains a particular character.

6. 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.

7. Computing a String's length

Write a recursive method that will compute a String's length. You may use only substring() and equals().

8. Computing if two Strings are equal

Write a recursive method that will compute whether or not two Strings are equal to each other in their contents. You may use only length(), charAt(), and substring().

9. Turn in

Create the script file as before. Be sure to begin by showing your program compiling. Run the program using a variety of words.

Turn in your source and script as lab5.

Do not turn in a printed copy.

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