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


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.


By the end of this lab, you should 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:

[[[ Download PC zip ]]]
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.*;


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.

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.

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

Last modified 10:04:34 CDT 02 August 1999 by Ron K. Cytron