Sierpinski Triangle

One simple graphical example of recursion is the Sierpinski triangle, which can easily be drawn by hand, which will help in determining how to write the algorithm.

Drawing a Sierpinski Triangle on paper

On a piece of paper:

1. draw a large, equilaterial triangle.
2. identify the midpoint of each of the three sides of the large triangle, and draw a new smaller triangle by connecting these midpoints.
3. Ignore the middle triangle that you just created, apply the same procedure to each of the three corner triangles (identifying the midpoints of their three sides, etc.).
4. Each time you create a new set of triangles, you recursively apply this procedure to the three smaller corner triangles. You could continue this process until you can no longer draw any smaller lines, but usually one stops after a few iterations.

Drawing a Sierpinski Triangle on the computer

We can draw Sierpinski triangles on the computer using any graphical library. Using Processing, and perhaps even the PTurtle module, we can write a program with a recursive function that creates Sierpinski triangles.

As you consider how to go about doing this, think about what the function will need to have for parameters. What will be the base case for our function? What will the recursive call look like, and what parameters will need to be modified when we make the recursive call?

One strategy for determining when the algorithm should stop is to think of the "degree" of the triangle (fractal). It begins with a degree of some value--say 3--and then each time we recurse, we reduce the degree of the triangle by 1. Once the degree reaches 0, we'll have arrived at the base case.

Create a Processing project SierpinskiTriangle that draws Sierpinski triangles.

Extension

Colored triangles, part 1

Sierpinski triangles have a certain appeal of their own, but they become even more interesting when the triangles are given different colors.

Begin by filling your triangle with a color, either black or white, based on the odd- or even-degree of the triangle.

if (degree % 2 == 0)
    fill(0);   // black
else
    fill(255); // white

Colored triangles, part 2

Once you've done that, consider expanding the range of colors that you use for the fill by creating a color map of colors that can be used in coloring your triangle.

In your instance variables create an Array of colors:

color[] map = {color(255,128,0), color(128,255,0), color(0, 128, 128)};

In your recursive function, identify the fill for each triangle based on the degree and the color map:

fill(map[degree % map.length]);