CS 101 (Spring 1999) Lab 4: Recursion

Lab Assigned Design Due
(Mondays 2 PM)
Lab Due
(Fridays 2 PM)
5 Feb 8 Feb 12 Feb

Overview:

Recursion is a powerful method for reasoning about and solving computational problems. A large problem is conceptually decomposed into smaller problems, each characterized in the same way as the large problem. Recursive programs tend to accomplish a lot with very little coding effort. Once you are accustomed to the style, recursive programs are easy to read and understand.

Goals:

By the end of this lab, you should
• 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"
This lab contains two parts, design and implementation, due on the dates shown above by 2 PM.

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.
Zip includes:

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.