CS 101 (Spring 1999) Lab 5: Persian Recursion and Slices of PI

Lab Assigned Design Due
(Mondays 2 PM)
Lab Due
(Fridays 2 PM)
12 Feb 15 Feb 19 Feb

Overview:

Programs with repetition can often be crafted using recursion or iteration. It is important to recognize which paradigm is appropriate for solving a particular problem. Recursive programs are useful when a large problem can be cast as smaller instances of itself. Recursive programs tend to be shorter, more elegant, but possibly less efficient than iterative versions (recall the Fibonacci program). Iteration is most appropriate when elements of a space must be visted repeatedly. Also, many tail-recursive programs are clearer when written iteratively.

Goals:

By the end of this lab, you should
• Gain more experience with recursive solutions and programs
• Know how to use loop constructs to create iterative solutions
• Be able to "think iteratively"
• Know how to use a random-number generator
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: In this lab, you will have to create your own project to manage your code. After you unzip the files into a Lab5 folder, follow these steps to create the project.
1. After unzipping, there should be a Lab5 inside your cs101 folder.
2. Start up Symantec Cafe and select the "New" option in the Project menu.
3. In the "Directories" area of the dialog box, select the Lab5 folder you created in Step 1.
4. Type `Lab5.prj` in the area labeled "Project Name" and click the "Next>" button.
5. Change the "Target Type" to be `Application` (not Applet).
6. Fill in the "Main Class" as `Lab5`
7. On the next page, add the .java files to your project.
8. Click the "Finish" button. Your project will be created and opened for editing.
9. To create a file of your own, such as `PersianRug.java`, create the file using the "File" menu. Save the file into your Lab5 folder using the name you want (e.g., `PersianRug.java`).

When you save the file, check the "add to project" option in the dialog box, so that the file will be recognized as part of the project.

NOTE: If you forget to check the "add to project" box when you save a file for the first time, the classes and methods won't be found by the compiler. To fix this, you can save the file again using "Save as" and check the box, or you can go to the "Edit" option in the Project menu to add the file to the list of Project files.)

You'll want to type the following lines at the top of any files that use the terminal or canvas classes.

```import cs101.terminal.*;
import cs101.canvas.*;
```

Particulars

Persian Recursion

The idea for this lab appeared in the article "Persian Recursion", by Anne M. Burns, Mathematics Magazine, volume 70, 1997, pages 196-199.
Design and implement the class `Persian.java` that does the following.

• Initially (when the constructor is called), a square of a supplied size is drawn. The color of each edge of this square is the same color.
• Repeatedly, a square S is subdivided into four quadrants by placing a horizontal and vertical line through the middle. The color of these two lines is identical, and is some function of the colors of S's edges.
• This algorithm is replied recursively to the resulting 4 subquadrants.
• Recursion stops when further subdivision cannot contribute to the picture. (You have to come up with the termination condition as part of your design.)
The effect is to make a picture that looks like a Persian rug. To see this effect, run the sample solution.

For the purpose of this lab, it is helpful to regard color as an integer. This is a kind of abstraction that allows us to compute one color as the function of other colors. You are supplied with the class `Crayon.java`, 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.

You will have to invent a function that takes four colors (the colors of a square's sides) and computes what color the middle (subdividing) lines should be. Let c1, c2, c3, and c4 represent the (`int`) color of each of the four sides of a square. If the initial square's sides are color 0, then a bad function would be:

```  (c1 + c2 + c3 + c4)
```
because the result would always be 0. For the design don't worry about the particular function---worry only about its type signature. However, for the implementation you will experiment with a few functions:
1. Find a function that always draws the same color
2. Find a function that always alternates between two colors
3. Find a function that uses all the colors

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

PI by Throwing Darts

If a dartboard of radius r is placed inside a square whose sides are each 2r, then we can compute PI by thowing darts as follows.

• Each dart must land somewhere in the square--perhaps inside the dartboard, perhaps not.
• The ratio of the areas of the dartboard to the square is PI/4.
• Let in represent the number of darts that land in the dartboard. Let total represent the total number of darts thrown.
• The ratio of in/total appraoches PI/4.
` DartBoard.java `
As provided, this class contains a circle and a square. The two objects are drawn on a CS101Canvas. You must modify this class so that it can be used to compute PI, when called from `Startup.java`. Your design here will be graded on how generally you approach the API for `DartBoard`. For example, giving the class a `computePI` method is too heavy handed, but there may be methods you could provide that would be useful for PI and for using `DartBoard` in a darts game.
` Math.random `
Random numbers play an important role in almost any simulation. In this case, we want to simulate darts thrown into a square. We therefore must simulate the dart thrower. It would not do simply to flip a coin at each throw and ask if the coin landed in the dartboard. The resulting ratio would approach 1/2 and not PI. We must be more careful about accounting for where the dart lands.

It is helpful to know that ` Math.random ` returns a `double` value d such that

```     0.0   <      d     <   1.0
-
```
Thus, if we want an integer between 0 and 51, we can compute
```  int rnumb = (int) (52 * Math.random())
```
The `(int)` in the expression above demands a narrowing cast from `double` (the default value of the parenthesized expression) to `int`. Java will keep the integer portion of the resulting computation.

Once your simluation is implemented, compute values for PI when 10, 100, 1000, and 10000 darts are thrown. Print these values out using `Terminal.println`.

PI by Wallis

The English mathematician Wallis is credited for the following method of computing PI/4:

``` PI        1       1       1       1       1
----  =   ---  -  ---  +  ---  -  ---  +  ---  - .......
4         1       3       5       7       9
```
In `Startup.java`, create and call a method to compute PI iteratively using the formula above. Print the result of your computation using `Terminal.println` after 10, 100, 1000, and 10000 iterations.

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.
• Define your `PersianRug` class. Give its API and describe what the methods do.
• How will you terminate the recursion in `PersianRug`? In Lab 4, we stopped when a rectangle of a specified minimum width was achieved. For this lab, you must ensure that every pixel gets colored.
• What methods will `DartBoard.java` have? Give their API and describe what they do.
• How will you use `DartBoard.java` to compute PI?
Implementation (due Friday)
1. Implement the PI computation and the Persian Rug problem.
2. Complete a code cover sheet.
3. Provide printouts of any files you created or modified for this assignment.
4. Provide transcripts of your experiments to compute PI (both by darts and using Wallis).
5. Be prepared to demo your Persian Rug in lab, including any of the color functions mentioned above. Be sure to count the number of recursive calls, and print the answer using `Terminal.println`.
6. Be prepared to say which of the two methods for computing PI works better.