Java Reference
In-Depth Information
system uses stacks to manage the calls behind the scenes. To some extent, recursion provides
a level of abstraction that hides iterations and other details from the user.
20.19
How many times is the
moveDisks
method in Listing 20.8
✓
✓
invoked for
Check
moveDisks(5, 'A', 'B', 'C')
?
Point
Using recursion is ideal for displaying fractals, because fractals are inherently recursive.
Key
Point
A
fractal
is a geometrical figure, but unlike triangles, circles, and rectangles, fractals can be
divided into parts, each of which is a reduced-size copy of the whole. There are many inter-
esting examples of fractals. This section introduces a simple fractal, the
Sierpinski triangle
,
named after a famous Polish mathematician.
A Sierpinski triangle is created as follows:
VideoNote
Fractal (Sierpinski triangle)
1. Begin with an equilateral triangle, which is considered to be a Sierpinski fractal of order
(or level)
0
, as shown in Figure 20.9a.
2. Connect the midpoints of the sides of the triangle of order
0
to create a Sierpinski trian-
gle of order
1
(Figure 20.9b).
3. Leave the center triangle intact. Connect the midpoints of the sides of the three other tri-
angles to create a Sierpinski triangle of order
2
(Figure 20.9c).
4. You can repeat the same process recursively to create a Sierpinski triangle of order
3
,
4
,
. . . , and so on (Figure 20.9d).
The problem is inherently recursive. How do you develop a recursive solution for it? Con-
sider the base case when the order is
0
. It is easy to draw a Sierpinski triangle of order
0
.
(a) Order 0
(b) Order 1
JPanel
JPanel
(c) Order 2
(d) Order 3
F
IGURE
20.9
A Sierpinski triangle is a pattern of recursive triangles.