## CS 101 (Fall 2000) Lab 4: Recursion -- Lost in the Woods

Author: Sergey Klibanov
Lab Assigned Design Due
(In class)

1 PM
Implement
(In Lab)
Demo
(In Lab)
Lab Due
(In class)
Friday
1 PM
2 Oct None 4-5 Oct 11-12 Oct 16 Oct

### Overview:

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.

### Goals:

By the end of this lab, you should:
• Have a better understanding of recursive algorithms
• Have more experience with API design.

### Before Starting:

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

Zip includes: ``` Forest.java TreeMakingListener.java Lab4.java ```

### 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 look nice.
• Each tree drawn must report the total number of branches it has.
 A starting schematic A finished tree with no randomness

### Design

There are two classes in this lab that you must design and create.
1. `Forest`
• 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 printed out.
2. `DirectionalBranch`
• For each branch in this lab, we will be interested in several characteristics:
1. Starting coordinates
2. Direction
3. Length
4. Ending coordinates
5. 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 characteristics.
• 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.

#### Hints

• 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...
``````	Point2D mypoint;
double xcoordinate=5;
double ycoordinate=4;
mypoint=new Point2D.Double(xcoordinate,ycoordinate);

double anotherxcoordinate=mypoint.getX();
double anotherycoordinate=mypoint.getY():
``````

At the beginning of a .java file using the Point2D class, you must put
``` import java.awt.geom.*;```
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 pixels.

### What to turn in:

1. Complete a code cover sheet.
2. Provide a printout of any files you have modified (see approach below).
3. Provide the JavaDoc printout for `DirectionalBranch`.
4. 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.

### Implementation:

1. 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 `import java.awt.geom.*;`
2. 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.
3. Add randomness one feature at a time.
4. 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?
Good luck!