Homework 4: Recursive Graphics

A. Goals

The purpose of the Recursive Graphics assignment is to gain practice with recursion.

B. Background

Read sections 2.1–2.3 of Sedgewick & Wayne. Review the H-Tree example from the textbook and lecture.

The Sierpinski triangle is an example of a fractal pattern, like the H-tree pattern from Section 2.3 of the textbook. The Polish mathematician Wacław Sierpiński described the pattern in 1915, but it has appeared in Italian art since the 13th century. Though the Sierpinski triangle looks complex, it can be generated with a short recursive program. Your tasks are to write a recursive program that draws the Sierpinski triangle and a second program that draws another design of your choosing using recursion.

This is a Sierpinski triangle:

Sierpinski triangle of order 9

Here's a fractal in polymer clay and a Sierpinski valentine. Have a fractal cookie, a Sierpinski hamentashen, or a Sierpinski candy corn video (check out her other videos while you're at it!):

In this assignment, you will write a program Sierpinski.java that recursively draws a Sierpinski triangle using PennDraw. These instructions will walk you through the process step by step.You are not allowed to use PennDraw.setXScale(), setYScale(), or any scale changing in this assignment. Doing so will only make the assignment harder.

A. The triangle() function

First, write a function triangle() that takes a side length sideLength and a pair of coordinates (x, y) as parameters and uses PennDraw.filledPolygon() to draw a filled, upward-pointing equilateral triangle. You may use whichever form of PennDraw.filledPolygon() you prefer. It is up to you whether to define your triangle() function such that x and y specify the location of the triangle center, a particular vertex, or any other position in the triangle.

You can make your triangles any color(s) you like. Please do not add a background.

Use the figure below to work out the coordinates of the other two vertices of the triangle, given one vertex:

Sierpinski triangle geometry

Make sure that your code compiles.

B. The main() function

Write a main() function that calls your triangle() function to draw a triangle with sides of length 0.5 with the top vertex located at (0.5, √ 3 / 2 )

Later you will modify main() to draw the full Sierpinski triangle.

When you compile and run your program, you should see a triangle in the center of your window, somewhat in the upper portion.

C. Setting up the recursive structure of sierpinski()

Write a function sierpinski() that takes two parameters, numLevels and size. Your function should print numLevels and size, before recursively calling itself three times with the arguments numLevels - 1 and size / 2. The recursion should stop when numLevels is less than 1. Later, you will replace the print statements with a call to triangle().

Modify main() to interpret its first command-line argument as numLevels. Have it call sierpinski(numLevels, 0.5). You may assume that your program will be run with exactly one command-line argument that is a positive integer.

Make sure that your code compiles.

D. Checkpoint

Running your program with the following command-line arguments should produce the following output:

          > java Sierpinski 0

(no output)

> java Sierpinski 1
          1 0.5
> java Sierpinski 2
          2 0.5
          1 0.25
          1 0.25
          1 0.25
> java Sierpinski 3
          3 0.5
          2 0.25
          1 0.125
          1 0.125
          1 0.125
          2 0.25
          1 0.125
          1 0.125
          1 0.125
          2 0.25
          1 0.125
          1 0.125
          1 0.125

E. Drawing the Sierpinski triangle in sierpinski()

Comment out the print statements from Sierpinski().

Modify sierpinski() to take two additional arguments, x and y, and draw a Sierpinski triangle of order numLevels of size size with a vertex at (x, y).

Think recursively. A Sierpinski triangle of order numLevels comprises just a solid triangle and three smaller Sierpinski triangles, each half the size of the original, each of order numLevels - 1, to the left and right and below it. You have already written the function to draw the triangle and the recursion code from the previous steps – now, you only need to make the correct function calls.

Warning Do not call, PennDraw.setCanvasSize(), or PennDraw.save(). These functions will break our test scripts, and you will receive a large point deduction.

F. Checkpoint

Running your program with the command-line arguments below should produce the following output. Note that as numLevels increases, the figure's "bottom" approaches the "bottom" of the window (The figures below have a light outline around the triangle for illustration. You do not need to draw this outline in your own program.)

Sierpinski triangle of order 1 Sierpinski triangle of order 2 Sierpinski triangle of order 3
> java Sierpinski 1 > java Sierpinski 2 > java Sierpinski 3
Sierpinski triangle of order 4 Sierpinski triangle of order 5 Sierpinski triangle of order 6
> java Sierpinski 4 > java Sierpinski 5 > java Sierpinski 6

G. Animating

Once you have your Sierpinski triangle working, add calls to PennDraw.enableAnimation() and PennDraw.advance() into your sierpinski() function. (You are not required to animate your Sierpinski triangle, and it is not worth any points, but it is fun and will help you visualize the recursion. If you do add animation, leave it in your code: it will not affect our grading scripts.)

Experiment with different arrangements of the recursive calls to sierpinski() and your call to the triangle() function.

In this part you will create your own recursive pattern. Write a program Art.java that takes one integer command-line argument n to control the depth of the recursion and produces a recursive pattern of your own choosing.

It's up to you what to write, as long as it follows the rules below.

Extra credit You will receive up to two points of extra credit for especially creative submissions, as judged by the graders. Extra credit will be rewarded not only for especially cool recursion, but also for especially cool designs, even if the recursion is fairly simple. As long as your Art.java meets the minimum requirements (takes one command-line argument, is not tail-recursive, stays within the unit square, and is fundamentally different from our examples), it will be eligible for extra credit.

Be creative and have fun!

Warning Teaching staff are unable to answer questions such as "Is my Art.java good enough to get full credit?" or "Is my Art.java cool enough to get extra credit?" You will need to decide for yourself. We do not grade homework before it is submitted, and we will not promise in advance that something is correct.

Examples

Check out the Famous Fractals in Fractals Unleashed, and Wikipedia's list of fractals by Hausdorff dimension. Some pictures are harder to generate than others (and some require trig); consult a TA for advice if you're unsure.

Some examples from the lists above that fulfill the requirements for Art.java are shown below.

Cantor Set

Sierpinski Carpet

Dragon Curve Moore Curve

Submit a completed readme_sierpinski.txt, Sierpinski.java, Art.java, and if desired, an extra.zip file containing any supplementary files needed by Art.java.