CS 101 (Spring 1999)
Lab 5: Persian Recursion and Slices of PI
(Mondays 2 PM)
(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.
- 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
The design will be discussed Monday in class.
your graded design will be returned.
No other handouts or code will be issued. So, think
carefully about your design!
[[[ Download PC zip ]]]
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.
Read over this entire document before you start.
- Study the recursion examples given in class.
- If you need help, please ask.
- After unzipping, there should be a Lab5 inside your cs101 folder.
- Start up Symantec Cafe and select the "New" option
in the Project menu.
- In the "Directories" area of the dialog box,
select the Lab5 folder you created in Step 1.
the area labeled "Project Name" and click the "Next>" button.
- Change the "Target Type" to be
Application (not Applet).
- Fill in the "Main Class" as
- On the next page, add the .java files to your project.
- Click the "Finish" button. Your project will be created and opened
- To create a file of your own, such as
create the file using the "File" menu. Save the file into
your Lab5 folder using the name you want (e.g.,
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
- 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
does the following.
The effect is to make a picture that looks like a Persian rug.
To see this effect, run the sample solution.
- 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.)
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
Crayon.pick(int). Given any integer, the method
will return a
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 (
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:
- Find a function that always draws the same color
- Find a function that always alternates between two colors
- 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
- 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.
- As provided, this class contains a circle and a square.
The two objects are drawn on a
You must modify this class so that it can be used to compute PI, when called
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
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
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())
(int) in the expression above demands a narrowing
double (the default value of the parenthesized
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
- 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
Startup.java, create and call
a method to compute PI iteratively using the formula above. Print the result
of your computation using
after 10, 100, 1000, and 10000 iterations.
What to turn in:
- Design (due Monday)
- Complete a design cover sheet.
- As usual, describe the classes and the method APIs you will use for
- Define your
PersianRug class. Give its API and
describe what the methods do.
- How will you terminate the recursion in
In Lab 4, we stopped when a rectangle of a specified
minimum width was achieved. For this lab, you must ensure that every pixel
- What methods will
have? Give their API and describe what they do.
- How will you use
to compute PI?
- Implementation (due Friday)
- Implement the PI computation and the Persian Rug problem.
- Complete a code cover sheet.
- Provide printouts of any files you created or modified for this
- Provide transcripts of your experiments to compute PI (both
by darts and using Wallis).
- 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
- 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