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:

Before Starting:

[[[ Download PC zip ]]]
Zip includes:

Problem Description: Drawing a tree

You must implement the following recursive algorithm for drawing a tree:


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

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


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!

Last modified 21:18:52 CDT 02 October 2000 by Ron K. Cytron