Overview:

Goals:

• Understand the concepts of recursion, base case, termination condition, and recursive call
• Be able to read, understand, and hand-simulate recursive procedures using the substitution model
• Be able to write recursive procedures from English specifications of arithmetic problems
• Be able to "think recursively"

The design will be discussed Monday in class. In Lab, your graded design will be returned. No other handouts or code will be issued. So, think carefully about your design!

Before starting:

• Read over this entire document before you start.
• Study the recursion examples given in class.
• If you need help, please ask.

• Lab4.java
• Startup.java
• Crayon.java
• Recurse.java

Particulars

For each of the following problems, you will design and then implement a recursive procedure to solve the problem. In order to show the recursion unfolding, you should instrument each procedure to print its parameters and return values (if any), as shown in the factorial example in Recurse.java.

1. Design and implement a recursive (static) method sumDownBy2 to be placed in Recurse.java with the following specification.

   PARAMETERS:   a positive integer n
   RETURN VALUE: the sum of the positive integers n + (n-2) + (n-4) + ...
   EXAMPLES:     sumDownBy2(7) is 7+5+3+1 = 16
                 sumDownBy2(8) is 8+6+4+2 = 20
                 sumDownBy2(0) is 0
                 sumDownBy2(-1) is 0
   

   Test your method by calling it from Startup.java as in

      int sdb = Recurse.sumDownBy2(7);
   

   Do several such tests, and print out the results with an informative message.

2. Write a recursive (static) method taylorE to be placed in Recurse.java with the following specification.

   PARAMETERS:   a positive integer, n
   RETURN VALUE: the (double) sum:
   
       1          1         1         1              1  
      ---   +    ---   +   ---  +    ---  +  ... +  ---
       0!         1!        2!        3!             n!
   
   EXAMPLES:     taylorE(0) is 1/0! = 1.0
                 taylorE(1) is 1/0! + 1/1! = 2.0
                 taylorE(2) is 1/0! + 1/1! + 1/2! = 2.5
                 taylorE(3) is 1/0! + 1/1! + 1/2! + 1/3! = 2.66666
   

   Test your method and print results by calling it from Startup.java.

   Hint: By all means, use the factorial method provided in Recurse.java. Get rid of the tracing output in factorial if it interferes with your own output or if you find it annoying.

3. Write a recursive method taylorOneOverE to be placed in Recurse.java with the following specification.

   PARAMETERS:   a nonnegative integer, n
   RETURN VALUE: the (double) sum:
                                                        n
       1          1         1         1             (-1)
      ---   -    ---   +   ---  -    ---  +  ... +  ---
       0!         1!        2!        3!             n!
   
   EXAMPLES:     taylorOneOverE(0) is 1/0! = 1.0
                 taylorOneOverE(1) is 1/0! - 1/1! = 0.0
                 taylorOneOverE(2) is 1/0! - 1/1! + 1/2! = 0.5
                 taylorOneOverE(3) is 1/0! - 1/1! + 1/2! - 1/3! = 0.3333
   

   Hint:

       a - ( b - ( c - ( d - e)))
   =   a -   b + ( c - ( d - e)))
   =   a -   b +   c -   d + e
   

4. If you repeatedly go half way to your destination, will you ever get there? The answer is "no, but you can get arbitrarily close." Design and implement a class whose constructor takes in two parameters. One parameter represents a rectangle (perhaps by its width and height, perhaps by its corners -- this will show up in your design). The other parameter is an integer called "min" that specifies how close you will draw the lines before stopping. The constructor for this class should instantiate a CS101Canvas and then call a recursive line-drawing method (within the same class) with the following specification:

      INPUT:  Rectangle r
      RESULT: if the width of r is less than min, just return
              otherwise, draw a vertical line that subdivides the rectangle
              in two, and then recurse on the right half of the rectangle
      RETURN: nothing (void)
   

   Place code in Startup.java to test your class on rectangles of width 64, 128, and 256. Use a min value of 5.

   Place code in your class to count how many times your recursive method is called from within the class. At the end of the computation, print out this number (with a nice message) using Terminal.println.

5. Divide and Conquer: Design and implement another class, which is a modified version of your solution to the previous problem. For this problem, you will recurse on both the left and right halves of the rectangle.

   For example, if the rectangle has width 64, you'll draw a line at 32 and then recurse on each of the two smaller rectangles. In those recursive calls, lines will be drawn at 16 and 48, and each will result in two more recursive calls. So, you'll get lines at 8, 24, 40, and 56. Each of those will result in two more recursive calls, so you'll draw lines at 4, 12, 20, 28, 36, 44, 52, and 60. Since those rectangles have width less than 5, the recursion will end. The final result, then, will be a rectangle 64 pixels wide divided into 16 rectangles, each of width 4.

   This time, you will alternate the colors of your rectangles, by using the Crayon.java class, which contains the method Crayon.pick(int). Given any integer, the method will return a Color. Internally, the method maintains 16 different colors, indexed by the integers 0 through 15. Your recursive rectangle renderer should step through these colors so that the lines you draw for the first rectangle are colored 0, the second rectangle's new lines are colored 1, and so on.

   Place code in your class to count how many times your recursive method is called from within the class. At the end of the computation, print out this number (with a nice message) using Terminal.println.

What to turn in:

Design (due Monday)

1. Complete a design cover sheet.
2. As usual, describe the classes and the method APIs you will use for this lab. Where possible, do not pass multiple parameters that are part of the same object. Instead, wrap them up in an object you define.
3. For the recursive problems, describe your approach:
   • What are the parameters of the recursive method?
   • For what values of the parameters will your method work?
   • For what parameter settings will recursion terminate?
   • What is the overall idea behind your recursive method?

Implementation (due Friday)

1. Complete a design cover sheet.
2. Implement each method as described above. The mathematical methods go in Recurse.java. However, but the graphical problems each go in a separate class.
   • You will have to edit a new .java file for each such class.
   • You may have to add these files into the project using the Project...Edit menu.
3. Provide transcripts of the tests you do on the mathematical methods.
4. Provide transcripts showing the number of recursive calls for the graphical methods.