CS211 Assignment 1: Recursion
Due Tuesday, 11 September, IN CLASS



What to hand in: Hand in a copy of file RecursionTest.java, which should contain all the functions that you wrote. Here is what must be included:

  1. At the top of file RecursionTest.java, include a comment that gives your name, id number, recitation number and time, and recitation instructor.
  2. WITH EACH FUNCTION that you write, INCLUDE A COMMENT that lists the test cases (the arguments used in calls to the function) you used when checking the function!  You must include enough test cases for you and us to have 99.9% confidence that the function is correct. Your grade will depend on the test cases that you used.
  3. Hand in also a sheet of paper with the answers to question 9. Attach it with a stapler to your listing of RecurstionTest.java.
Introduction: The purpose of this assignment is to get you to write several recursive functions and procedures, so that you achieve some skill in writing them. Of course, LOOPS SHOULD NOT BE USED. Also, we ask you to execute a recursive procedure yourself, so that you understand how execution of a call works.

Your methods should be placed in this file: RecursionTest.java. You will also need file  JLiveWindow.java. Class RecursionTest contains method main. When you run this program, a GUI appears on your monitor, with a number of int fields, double fields, and String fields. You can change a call in method main to change the number of fields that appear. Whenever button Ready! is pressed, method RecursionTest.buttonPressed is called. You can use this method as a test driver, as discussed next.

In order to test a function, change method RecursionTest.buttonPressed to input one or more data items from the GUI, call the function, and display the results of the function call in the GUI. This allows you to test many cases with one execution of the program. You should test each function thoroughly, with enough, properly chosen, test cases that give you 99.9% confidence in its correctness.

NOTE: Write a precise specification of a function before writing the body of the function. Use proper indentation. A program without proper method specifications or proper indentation will be returned ungraded, and you will receive a late penalty when you hand it in after fixing it.

0. Write a method that produces String s with every character duplicated (You don't have to do anything with this exercise; it is an example).

       // = s but with every character duplicated
       public static String duplicate(String s) {
            if (s.length() == 0)
                 { return s;  }
            // { s has at least one character }
                 String temp= duplicate(s.substring(1));
                 return s.substring(0,1) + s.substring(0,1) + temp;
       }

1. Write a method that returns a String that contains all the capital letters of String s. Use the following if-condition to determine whether character number i of String s is a capital letter:

    'A' <= s.charAt(i)  &&  s.charAt(i) <= 'Z'

2. Write a method that removes adjacent duplicates from a String s, e.g. for s = "aabbbbc", the answer is "abc".

3. Write a method that produces String s but with characters numbered 1, 3, 5, 7, ... removed.

4. Write a method that produces String s but with its characters reversed. Do it using this idea: The reverse of a String c1 + s + c2, where c1 and c2 are characters, is c2 + (reverse of s) + c1.

5. Write a method that returns the number of blank characters '  ' in a string.

6. Write a method that produces the greatest common divisor of two positive integers. Use the following facts:

  1. The greatest common divisor of a and a is a.
  2. If b < c, the greatest common divisor of b and c equals the greatest common divisor of b and c-b.
  3. Greatest common divisor is a symmetric operation: the greatest common divisor of b and c equals the greatest common divisor of c and b.
7. Write a method that determines whether some integer in the range b..c (for b <= c) divides n. For example, hasDivisor(3,9,20) is true, because some integer in the range 3..9 divides 9. But hasDivisor(3,9,23) is false.

8. Write a method that tests whether some integer is prime. (A prime is an integer that is greater than 1 and is divisible by no positive integer other than 1 and itself.) Make use of the function you wrote in the previous exercise.

9.  Execute the assignment String t= duplicate("ab");  where function duplicate is given in exercise 0. Draw all the frames. We want snapshots of the call stack s just before each execution of the body of method duplicate. Label each snapshot clearly.

Information on Strings:  Read pages 35-37 of Weiss for information on Strings. In addition, here are the basics that you need. Strings are immutable; you cannot change them. But of course you can create new ones. The characters of a String s are numbered 0, 1, 2, ..., s.length()-1.
 

String s= "";  Declare a String s, with initial value "" (the empty String).
s + t  Produce a String that consists of the chars of String s followed by the chars of String t (called "catenation").
s.length()  The number of characters in String s.
s.charAt(i) Character i of String s (this is of type char)
s.substring(i) The substring consisting of characters i, i+1, ..., s.length()-1.
s.substring(i,j) The substring consisting of characters i, i+1, ..., j-1.
s.equals(t) true iff Strings s and t are the same. Do NOT use  s == t  for this, for reasons to be explained later.