CS 112 Lab 5: Recursion and Graphics

In this lab we will learn how to use a simple graphics class and practice the concept of recursion which was introduced in CS 111. Graphics is a natural domain for recursion, and the intuition gained by observing the graphical display of recursive algorithms is useful for understanding recursion. It's also a lot of fun!

Java Graphics using StdDraw

We will be using a library of Java methods called StdDraw.java. It provides a number of primitives for drawing lines, squares, circles, and polygons. You simply need to download StdDraw.java and put it in the same directory/folder as your program RecursiveGraphics.java, and then you can call various methods to draw geometrical objects on a window that will pop up automatically. If you compile and run StdDraw.java, it will run its unit test main method to show a couple of its features (download the program and do this now!).

You may find a brief explanation of the StdDraw class here; the following is summary of the most important points.

For this lab, we will use the StdDraw library in combination with recursion to draw various interesting graphics that illustrate the power of recursion. The most important things to know about the StdDraw library is that it draw various shapes in a window that represents the range of points between 0 and 1 for x and y in the first quadrant of a Cartesian coordinate system:


Problem 0

Now we will look at how recursion can be used to draw interesting figures. Look at the template RecursiveGraphics.java, and examine the main method, where you see several methods called in the main method. The first one is drawSpiral(1000). It will display a recursively-drawn spiral.

(i) Look at the code and find the place where the parameters for the recursively-drawn circles are modified at each recursion, in lines 14 and 15. Try running the program with different values for these parameters, in the range 0.9 to 0.999. Look at the code and see if you can understand how recursion is used to draw the same thing over and over in different sizes and positions.

(ii) Similarly, you may comment out the call to drawSpiral(1000) and uncomment the call to drawHTree(10). Note again how this figure is drawn recursively. Now I want you to comment in and out the recursive calls to drawHTreeHelper(...) in lines 52-53 and 58-59 and see if you can predict how the drawing will change. Also, change the recursion depth from 10 to 5 or 15 and see how this affects the drawing.

There is nothing else to do for this problem: I just want you to get some experience with recursively-drawn graphics.

Problem 1

Now look at the method drawSquares(...). If you go to main and comment in the call drawSquares(100), you will see that it draws only a single square. This is because each recursive call just draws the same shape 100 times! However, if you make a small change to the values for x, y, or r in line 68 you will see that the drawing will change.

(A) Try various increments for each of these, or all of them, and try to make a drawing that looks something like this:

(B) Now, create another method drawCircles(...) which does something similar with circles. Just try to make something similar, no exact requirement here.

Problem 2

Now we are going to draw series of concentric circles and squares which are "filled" with the pen color, white or black, and we will change the pen color at each recursive call, to get something that looks like this:

In order to do this, you will need to complete the recursive helper method drawCSHelper by adding the appropriate recursive call (see the code).

Problem 3

Next we are going to draw a famous shape called the Sierpinski Triangle, which will end up looking like this:

To do this, you will need to complete the method drawSTHelper(...). The method drawSierpinskiTriangle(..) draws a black triangle, and then changes the pen color to white and starts to draw upside-down triangles inside each black triangle. Currently, it only draws one white triangle: you must write the recursive calls to continue to fill the black triangles with white triangles.

Here are the details of how to calculate the parameters at each recursive call. At each recursion level, the size of the triangles is halved, and they are drawn around the previous triangle as follows. If you draw a triangle with sides of length s, with lowest point (x,y), then you must recursively draw three triangles with sides of length s/2 at the locations shown here:

Your task for this problem is to complete the helper method drawSTHelper(...) with the appropriate recursive calls. Then uncomment the call to drawSierpinskiTriangle(10) and try it with various recursion depths.

Problem 4

Finally, we will draw a Sierpinski Carpet, which is similar to the Triangle, but make with with squares:

To do this, again you must complete the recursive helper method drawSCHelper(....) by filling in the recursive calls. This time, you will think of the square as a tic-tac-toe board: fill in the center square with white, and then recursively do the same thing to the other 8 squares, according to the following diagram (remember that to draw a square, you specify the center and the radius):

Just for fun....

You might want to try changing the shapes in the last problem, you could draw circles instead of squares, or circles at even depths and squares at even depths. You can also change the colors. Look at the method changeColorByRecursionDepth(....) which you can call before you draw something, and it will set the color according to the recursion depth.

What to Submit

Submit your code RecursiveGraphics.java with a main that has calls to all the methods commented out, except for the last one, the Sierpinski Carpet. When we run your code, it should draw the Sierpinski Carpet. Feel free to play around and be creative, especially by changing the colors!