12.5. Example: Drawing (Recursive) Fractals
is a geometric shape that exhibits a recursive structure. When it is divided into
So fractal patterns are all around us. Because of their
12.5.1. Nested Squares
Earlier in this chapter, we developed a recursive definition for drawing a nested squares pattern (Fig. 12.2). Now let's develop a recursive method that actually draws the pattern. For this pattern, the base case is the drawing of the square. The recursive case, if more divisions are desired, is the drawing of smaller patterns within the square:
Draw a square. If more divisions are desired draw a smaller version of pattern within square.
An important consideration for this algorithm is to specify precisely what we mean by "if more divisions are desired." In other words, how exactly do we control the recursion? In our earlier definition of the pattern, we used the length of the side to control the algorithm. When side 5, we recursed.
How should we represent the problem?
Levels of recursion
Another more general way to do this is to describe the fractal structure in terms of its levels . For nested squares, the level-zero pattern would be just the basic square shape (Fig. 12.21). A level-one pattern would be the basic square shape plus an inner square, and so on. The higher the level, the more subdividing we do. Therefore, one way to control the recursion is to use a level parameter as the recursion parameter the parameter that controls the recursion:
Draw a square. If the level is greater than 0, draw a smaller version of pattern within square.
Figure 12.21. Levels 0, 1, and 4 of the nested squares pattern.
What other parameters will we need for this method? If we're going to draw a rectangle, we'll need parameters for its x - and y -coordinates. We'll also need a parameter for the length of the sides of the square. Another issue we need to decide is how much the length of the sides should change at each level. Should length change by a fixed amount, by a fixed ratio, or by some other factor? In order to allow this kind of flexibility, let's use another parameter for this value.
These design considerations suggest the method shown in Figure 12.22. Note that we must also provide a Graphics parameter so that the method can use the drawRect() method to draw the square. As we decided, the level parameter controls the recursion. Its value is decreased by 1 in the recursive call. This ensures that level will eventually reach 0, and recursion will stop.
Figure 12.22. The drawBoxes() method.
Finally, note the use of the
parameter, which is used to change the length of the sides by a fixed amount,
2 * delta
, at each level. It is also used to calculate the
-coordinates for the location of the
Effective Design: Levels of Recursion
12.5.2. The Sierpinski Gasket
Let's return now to the
pattern that we introduced at the start of the chapter. This is a much more interesting fractal pattern (Fig. 12.24). The overall shape of the pattern is that of a triangle, but note how the outer triangle is divided into three smaller triangles. Then each of these triangles is divided into three smaller
Figure 12.24. Levels 0, 1, and 7 of the Sierpinski gasket fractal pattern.
Let's develop a recursive method to draw this pattern. If we follow the same strategy we used in the nested squares example, we get the following algorithm:
Base case: Draw a triangle. Recursive Case: If more divisions are desired, draw three smaller gaskets within the triangle.
For this pattern the base case is the drawing of the basic triangle. The recursive cases, if more divisions are desired, are the drawing of smaller gaskets within the triangle. Again we will use a level parameter to control the depth of the recursion. The higher the level, the more divisions will be drawn.
If we're going to draw a triangle shape, we need the coordinates of its three verticesthat is, an x - and y -coordinate for each vertex. Taken together, these design considerations suggest the method definition shown in Figure 12.25.
Figure 12.25. The drawGasket() method.
What other parameters do we need?
As we described earlier, we use the level parameter as the recursion parameter for this method, which controls the recursion. Each of the three recursive calls decreases the level by 1. This ensures that level will eventually equal 0, and recursion will stop.
Levels of recursion
Note how the three pairs of coordinates are used. Drawing a triangle is simple. Just draw three lines from
, and from
. The most complicated part of the method is calculating the vertices for the three inner gaskets. If you look at Figure 12.24 again, you will note that each of the inner triangles uses one of the vertices of the main triangle plus the
of the two adjacent sides. Thus, the triangle on the "left" uses the left vertex
, and the midpoints of the other two lines from
. As you may remember from high school math, the formula for computing the
Midpoint of a line
( (x1 + x2) / 2, (y1 + y2) / 2 )
This formula is used repeatedly to calculate the vertices of the three smaller gaskets.