Recursion - Data Structures and Problem Solving Using Java - page 309

figure 7.12
A recursively drawn
ruler

You do not have to understand the details of drawing lines and shapes in
Java to understand this program. You simply need to know that a Graphics
object is something that gets drawn to. The drawRuler method in Figure 7.13 is
our recursive routine. It uses the drawLine method, which is part of the Graphics
class. The method drawLine draws a line from one ( x, y ) coordinate to another
( x, y ) coordinate, where coordinates are offset from the top-left corner.
Our routine draws markings at level different heights; each recursive call
is one level deeper (in Figure 7.12, there are eight levels). It first disposes of
the base case at lines 4 and 5. Then the midpoint mark is drawn at line 9.
Finally, the two miniatures are drawn recursively at lines 11 and 12. In the
online code, we include extra code to slow down the drawing. In that way, we
can see the order in which the lines are drawn by the recursive algorithm.

fractal star
Shown in Figure 7.14(a) is a seemingly complex pattern called a fractal star,
which we can easily draw by using recursion. The entire canvas is initially
gray (not shown); the pattern is formed by drawing white squares onto the
gray background. The last square drawn is over the center. Figure 7.14(b)
shows the drawing immediately before the last square is added. Thus prior to
the last square being drawn, four miniature versions have been drawn, one in
each of the four quadrants. This pattern provides the information needed to
derive the recursive algorithm.

1 // Java code to draw Figure 7.12.
2 void drawRuler( Graphics g, int left, int right, int level )
3 {
4 if( level < 1 )
5 return;
6
7 int mid = ( left + right ) / 2;
8
9 g.drawLine( mid, 80, mid, 80 - level * 5 );
10
11 drawRuler( g, left, mid - 1, level - 1 );
12 drawRuler( g, mid + 1, right, level - 1 );
13 }

figure 7.13
A recursive method
for drawing a ruler