Computer Science 252
Problem Solving with Java

Fall 2013, The College of Saint Rose

Home     Syllabus     Schedule     Examples     Style Guide

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 (no groups larger than 2 permitted).

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

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

Sierpinski Gasket

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

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 not be part of 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 6 pixels for this threshold), do you actually draw a triangle (which we accomplish using 3 Lines).

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.

Stairs

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.

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 recursive data structure that would allow the objects to be modified or to answer queries.

Submitting Your Work

Before 11:59 PM, Tuesday, November 5, 2013, submit your Java program for grading. There are three things you need to do to complete the submission: (i) upload a copy of your Java program (the .java files only; submit each file separately) using Submission Box under assignment "Recursion", (ii) print a copy of your program and hand it to your instructor, and (iii) demonstrate the execution of your program for your instructor (2-day grace period for demos).

Don't forget to check your programs for compliance with the Style Guide for CSC 252 Programs

Note: you need not submit and/or 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 submit and print it.

Grading

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