RECURSION - Introduction to Java Programming: Comprehensive Version - page 722

This problem is inherently recursive. Using recursion makes it possible to find a natural, sim-
ple solution. It would be difficult to solve the problem without using recursion.
Consider tracing the program for n = 3 . The successive recursive calls are shown in
Figure 18.8. As you can see, writing the program is easier than tracing the recursive calls. The
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.

moveDisks(3,'A','B','C')

moveDisks(2,'A','C','B')
move disk 3 from A to B
moveDisks(2,'C','B','A')

moveDisks(2,'A','C','B') moveDisks(2,'C','B','A')

moveDisks(1,'A','B','C')
move disk 2 from A to C
moveDisks(1,'B','C','A')

moveDisks(1,'C','A','B')
move disk 2 from C to B
moveDisks(1,'A','B','C')

moveDisks(1,'A','B','C')
move disk 1 from A to B

moveDisks(1,'B','C','A')
move disk 1 from B to C

moveDisks(1,'C','A','B')
move disk 1 from C to A

moveDisks(1,'A','B','C')
move disk 1 from A to B

F IGURE 18.8

Invoking moveDisks(3, 'A', 'B', 'C') spawns calls to moveDisks recursively.

18.22

✓ ✓

How many times is the moveDisks method in Listing 18.8 invoked for
moveDisks(5, 'A', 'B', 'C') ?

Check

Point

18.8 Case Study: Fractals
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 18.9a.

2. Connect the midpoints of the sides of the triangle of order 0 to create a Sierpinski trian-
gle of order 1 (Figure 18.9b).

3. Leave the center triangle intact. Connect the midpoints of the sides of the three other
triangles to create a Sierpinski triangle of order 2 (Figure 18.9c).

4. You can repeat the same process recursively to create a Sierpinski triangle of order 3 , 4 ,
. . . , and so on (Figure 18.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 .
How do you draw a Sierpinski triangle of order 1 ? The problem can be reduced to drawing
three Sierpinski triangles of order 0 . How do you draw a Sierpinski triangle of order 2 ? The
problem can be reduced to drawing three Sierpinski triangles of order 1 , so the problem of