Java 7 for Absolute Beginners

CHAPTER 14 ■ RECURSION

Point2D.Double lowerLeft = new Point2D.Double(0, doubleHeight);
Point2D.Double lowerRight = new Point2D.Double(width, doubleHeight);
Point2D.Double top = new Point2D.Double(width / 2, 0);
drawTriangle(1, g, lowerLeft, lowerRight, top);
}
}

The SierpinskiTriangleJava class really starts in the paint method, where it calculates the corners
of the outer triangle and passes those values to the drawTriangle method. Then the drawTriangle
method calculates a series of triangles within triangles, down to the depth specified in the maxLevel
variable that is stated at the top of the class. You can change the depth by changing that value, and a
good exercise is to add setting that value to the user interface.
The actual drawing happens only after the class reaches the maximum level. At that point, there are
729 (3 to the 6th power) triangles that draw themselves and 364 triangles that contain other triangles.
Three hundred and sixty-four is not a power of 3, so how was that number obtained by calculating six
levels of depth? The following table shows the progression:

Table 14-1. drawTriangle Methods on the Stack, by Level of Recursion.

Step Number of Triangles

1 1

2 4

3 13

4 40

5 121

6 364

7 1093

As you can see, the inclusion of the outer triangle throws off the numbers a bit so that the total is
never a power of three. However, the difference between any two steps is a power of three. This kind of
pattern appears whenever a single item contains other items that scale in a regular fashion.
Within the drawTriangle method, I calculated the midpoints of the current triangle and created
three new triangles based on those points. That's the essence of the Sierpinski algorithm. The remaining
code in the method does the work of drawing and of making sure I don't miss the stop condition.