CS 101 (Fall 2000)
Author: Sergey Klibanov
Lab 4: Recursion -- Lost in the Woods
| || 2 ||Oct
|| 4-5 ||Oct
|| 11-12 ||Oct
|| 16 ||Oct
Recursive thinking is useful when a complex task can be
broken up into smaller instances of itself. Programs that
employ this method of reasoning are often much shorter than
iterative approaches, and much simpler to write. In this lab
you will design and implement classes that use recursion to display
a colorful tree on the screen.
By the end of this lab, you should:
- Have a better understanding of recursive algorithms
- Have more experience with API design.
- Read over the entire document before you start
- Check out the JavaDoc for this lab
- Run the sample solution
- Study the recursion examples given in class.
[[[ Download PC zip ]]]
Problem Description: Drawing a tree
You must implement the following recursive algorithm for drawing a tree:
- Initially, a line of length 30 is drawn upwards from a point specified by a mouse click. We will
call this line the trunk.
- Two branches are drawn from the endpoint of the trunk, each diverging 8 to 18 degrees
from the direction of the trunk and 90% of the trunk's length.
- For each branch drawn, two branches are drawn from its endpoint until one of the following conditions is met:
- The current branch is the 9th generation (the trunk counts as the first generation)
- As the tree progresses, we don't necessarily always
want branching to occur.
In particular, in the last 6 levels of recursion, each branch is given
a 70% chance of being placed (drawn).
Of course, if a branch is not drawn, then further
recursion along that particular branch should not occur.
- The color of the branch is a function of the recursion depth at which it is drawn. You can pick any color scheme you like; try to make it
- Each tree drawn must report the total number of branches it has.
A starting schematic
A finished tree with no randomness
There are two classes in this lab that you must design and create.
- This class, upon construction, creates a new window
in which the user can click, causing a tree to be drawn upwards from the click location.
- It has a
makeTree(int x, int y) method that
is called by the mouse listener to signal the creation of
a tree. That method should call a private recursive
method of your choice to actually draw the tree.
- After the tree is created, the number of branches in the
tree and the total number of branches in the forest is
- For each branch in this lab, we will be interested in
- Starting coordinates
- Ending coordinates
- The Line object that should be added
to the window to draw the branch
- This class will hold sufficient information about a
branch to easily report each of the above
- This class should be immutable.
We will give you a Forest class that creates a window and initializes
the mouse listener. This class will, however, have an incomplete
makeTree method that only draws the trunk. When you are creating a
functional method that draws a tree, consider what information
must be passed to each recursive call. This will probably include
but not be limited to the information needed to construct a DirectionalBranch object,
as well as the number of generations that have yet to be drawn.
It is OK (in fact, probaly unavoidable) if your recursive method has many many arguments.
You must create from scratch your own DirectionalBranch
class to gain experience in designing a class; this includes making
you own .java file for it. Carefully consider what
information the constructor of DirectionalBranch should take in
and what accessor methods it should have. Remember that DirectionalBranch should
be immutable, which means that once one is constructed, it cannot
be changed. You must turn in your design for DirectionalBranch as
the printout of a javadoc web page.
- Look at the Canvas Javadoc to
learn how to construct a Line of a specific color, or how
to set the color of a Line.
- To orient a Line in a certain direction on the screen, you can
use ShapeComponent's (and therefore Line's, because a Line is a
ShapeComponent) rotateAbout() method. For example, if you draw a line from
100,100 to 110,100 and rotate it -90 degrees about 100,100, you will get
a line going from 100,100 to 100,90. -90 degrees, because the increasing
direction for the Y axis is down instead of up in pixel coordinates.
- To calculate the endpoint of a rotated line, you could either
use a trigonometric approach or a simpler way using rotateAbout
that does not require you to do any math yourself.
- A method cannot return more than one piece of data. This makes returning
a pair or coordinates rather difficult with only one method. The solution is to
look in the Java 1.3 API for a class named Point2D to
hold a set of coordinates. For example, if I wanted to use that class to store a set of coordinates...
At the beginning of a .java file using the Point2D class, you must put
The reason to use Point2D instead of Point is that a Point will only store integer coordinates,
and when a line is rotated, the endpoint will probably not end up on an integer value. Remember
that Line objects exist in double-precision even though they are displayed on a screen made of integer-valued
What to turn in:
- Complete a code cover sheet.
- Provide a printout of any files you have modified (see approach below).
- Provide the JavaDoc printout for
- Provide a transcript from Startup's textual tests on your classes.
Recall that this file is produced automatically by the Transcript and can be
found in the file
transcript.txt in the same folder as your
Lab 4 files.
- You should start by implementing a functional DirectionalBranch class. An empty file is not given to you, you must create
your own .java file for it. Don't forget to
import canvas; at the top, and if you use Colors, also
import java.awt.Color;, and if you want to use Point2D, you should
- Continue by making a simple tree that has no randomness to it. The divergence angle should always be, for example, 15 degrees
and all branches before the 9th level of recursion should be drawn.
- Add randomness one feature at a time.
- For extra credit, you can experiment with different branching methods; for example what if there were 3 sub-branches instead of 2?
What if the original click produced 3 trunks instead of 1? Can you think of a way to draw a tree that looks like a Sierpinski gasket?
Last modified 21:18:52 CDT 02 October 2000
by Ron K. Cytron