RECURSION - Java Programming: From Problem Analysis to Program Design - page 892

Sample Run: (In this sample run, the user input is shaded.)
Enter a nonnegative integer in decimal: 57
Decimal 57 = 0111001 binary
PROGRAMMING EXAMPLE: Sierpinski Gasket
To draw the shapes of natural scenes, such as mountains, trees, and clouds,
graphic programmers typically use special mathematical tools, called fractals,
related to fractal geometry. Fractal geometry is a major area of research in
mathematics in its own right. The term fractal was introduced by the mathema-
tician Benoit Mandelbrot in the mid-1970s. Mandelbrot is credited with the
development of systematic fractal geometry, which provides a description of
many seemingly complex forms found in nature. One kind of fractal, called a
self-similar fractal, is a geometric shape in which certain patterns repeat, some-
times at different scales and with different orientations. Mandelbrot is recognized
as the first person to demonstrate that fractals occur in various places in mathe-
matics and nature.
Because certain patterns occur at various places in a fractal, a convenient and effective
way to write programs to draw fractals is to use recursion. This section describes a
special type of fractal called a Sierpinski gasket.
Suppose that you have the triangle ABC as given in Figure 13-9(a). Now determine
the midpoints P, Q,andR of the sides AB, AC,andBC, respectively. Next, draw
the lines PQ, QR,andPR. This creates three triangles, APQ, BPR,andCRQ,as
shown in Figure 13-9(b), which have similar shapes as in the triangle ABC.The
process of finding the midpoints of the sides and then drawing lines through those
midpoints is now repeated on each of the triangles APQ, BPR,andCRQ,asshown
in Figure 13-9(c). Figure 13-9(a) is called a Sierpinski gasket of order (or level) 0,
Figure 13-9(b) is called a Sierpinski gasket of order (or level) 1, Figure 13-9(c) is
called a Sierpinski gasket of order (or level) 2, and Figure13-9(d) shows a Sierpinski
gasket of order (or level) 3.