Computer Science 252
Problem Solving with Java

Spring 2014, The College of Saint Rose

Lab 6: Recursion Practice
Due: 11:59 PM, Tuesday, March 25, 2014

For this (hopefully short) lab leading up to our second exam, you will be working on drawing a few pictures that use recursion.

You may work alone or with a partner on this lab. Only one submission per group is needed.

There are lab questions a two-part programming assignment in this lab. Please refer to the "Submission Guidelines" on the course home page and syllabus for the requirements for each of these items.

Getting Started

In order for you to be able to focus only on the implementation of the recursive constructors, a starter BlueJ project is provided. Download and open this project to see the complete window controller class in class Recursion, and the skeletons of the two other classes whose constructors you will need to fill in: class Sierpinski and class Stairs.

As you can see, a very simple GUI has been created for you and mouse events handled so that you can specify the positions and sizes of the recursive objects. More on the specifics of those below.

Create a document where you will record your answers to the lab questions. If you use plain text, call it "lab6.txt". If it's a Word document, you can call it whatever you'd like, but when you submit, be sure you convert it to a PDF document "lab6.pdf" before you submit it.

A working solution for the programming assignment can be downloaded here.

A working solution for this program will appear below. Click inside the applet to interact with it.

Sierpinski Gasket

We will first work on drawing a variation on the Sierpinski gasket.

The gasket within a triangular area is drawn recursively. A gasket is actually 3 smaller gaskets, where each of the 3 smaller gaskets are within triangles defined by one corner of the original triangular area and the midpoints of the 2 incident sides of the original triangular area.

Question 1: For a gasket whose triangular area is defined by corners at (0,0), (0,100), and (100,0), give the coordinates of the 3 corners of each of the 3 gaskets at the first level of recursion. (3 points)

In class Sierpinski, you should fill in the constructor so that inside the triangle specified (which is drawn in the provided code but which should only be the base case of the recursion for your ultimate solution), 3 smaller triangles get drawn. Each corner of the large triangle should be a corner of one the smaller triangles, and the other corners of the smaller triangles are specified as the midpoints of the sides of the original triangle. In other words, instead of drawing the actual triangle connecting the three given points, you draw these 3 smaller Sierpinski objects. Only when you get to the base case, where the triangle specified is too small to be able to draw 3 smaller triangles inside (the demo uses a minimum length of 6 for all sides for this threshold), do you actually draw a triangle (which we accomplish using 3 Lines).

Note that Objectdraw's Location object has a distanceTo method that computes and returns the distance to another Location. You might want to make use of this to determine when the base case is reached.

When the radio buttons at the bottom of the window have "Gasket" selected, you can specify the 3 corners of the outline of the gasket to draw by pressing the mouse 3 times. Some visual feedback has been included showing a "rubber banding" effect when doing this.

Question 2: What instance variables would you need and how would you initialize them in the constructor if you wanted to provide methods such as move, contains, or removeFromCanvas? (3 points)


Your second task is to draw a staircase object in a particular way that lends itself well to recursion. We start with a square. Then just on top of the square (aligned with its left edge) and to the right of the square (aligned with its bottom edge), we draw 2 squares, each of which is half the size of the original. We now have what looks like a 3-step staircase. We can then do the same to the two smaller squares, resulting in 4 more squares, each a quarter of the size of the original, and we have a 7-step staircase. We continue this process until we would be drawing squares too small to bother with. In the demo, smaller squares continue to be drawn as long as they're at least 6 pixels tall.

Question 3: For a staircase whose largest square has an upper left corner at (100,100), size 100, give the coordinates of the upper left corner and size of the 2 stairs objects at the first level of recursion. (3 points)

When the radio buttons at the bottom of the window have "Stairs" selected, you can specify the upper left corner then the size of the base square (not of the entire staircase) with 2 mouse presses. Again, visual feedback is provided to show the outline of the base square.

Note: you might see some lines in your staircase that look like they don't quite line up or are double width (as is the case in the provided demo). This happens because of rounding errors as we divide the sizes by 2 at each step of the recursion. We could be more careful to ensure things line up, such as by restricting to int coordinates and sizes and making sure we start with a power of 2, but that is not necessary for our purposes.

Advanced Features

The above describes the required functionality. For up to 6 points of extra credit, you can add features. Possibilities include other recursive graphical objects, some meaningful color schemes for the lines that make up the gasket and/or the stairs, or developing a complete recursive data structure that would allow the objects to be modified or to answer queries.


Before 11:59 PM, Tuesday, March 25, 2014, submit your lab for grading. There are four things you need to do to complete the submission: (i) Copy your file with the answers to the lab questions into your project directory. Be sure to use the correct file name. If you prepared your answers in Word, export to a PDF file and submit that. (ii) Upload a copy of your lab (a .7z or .zip file containing your project directory) using Submission Box under assignment "Lab6". (iii) Demonstrate the execution of your programs for your instructor. (iv) Hand a printout of the Java files that make up the programming assignment to your instructor. (2 business day grace period for demos and printouts).

Note: you need not print the Recursion class, only the two classes you were required to modify. However, if you included any extra credit functionality that resulted in changes to that class, you should print it.


This assignment is worth 40 points, which are distributed as follows:

> FeatureValueScore
Lab Questions (9 points)
Lab Question 1 3
Lab Question 2 3
Lab Question 3 3
Style/Design/Documentation (8 points)
Comments 5
Style (names, declarations, constants) 2
Formatting 1
Sierpinski Correctness (12 points)
Correct sizes/positions 4
Recursive cases 5
Base case 3
Stairs Correctness (11 points)
Correct sizes/positions 4
Recursive cases 4
Base case 3
Extra Credit (up to 6 total)