Transcript 1 - Saint Mary's University | Mathematics & Computing Science

1
15
Recursion
 2005 Pearson Education, Inc. All rights reserved.
2
It's a poor sort of memory that only works backwards.
—Lewis Carroll, Alice in Wonderland
We must learn to explore all the options and possibilities that
confront us in a complex and rapidly changing world.
—James William Fulbright
Push on—keep moving.
—Thomas Morton
O! thou hast damnable iteration, and art indeed able to
corrupt a saint.
—William Shakespeare
Life can only be understood backwards; but it must be lived
forwards.
—Soren Kierkegaard
 2005 Pearson Education, Inc. All rights reserved.
3
OBJECTIVES
In this chapter you will learn:
 The concept of recursion.
 How to write and use recursive methods.
 How to determine the base case and recursion
step in a recursive algorithm.
 How recursive method calls are handled by
the system.
 The differences between recursion and
iteration, and when it is appropriate to use
each.
 2005 Pearson Education, Inc. All rights reserved.
4
15.1
Introduction
15.2
Recursion Concepts
15.3
Example Using Recursion: Factorials
15.4
Example Using Recursion: Fibonacci Series
15.5
Recursion and the Method Call Stack
15.6
Recursion vs. Iteration
15.7
String Permutations
15.8
Towers of Hanoi
15.9
Fractals
15.10
Recursive Backtracking
15.11
Wrap-Up
15.12
Internet and Web Resources
 2005 Pearson Education, Inc. All rights reserved.
5
15.1 Introduction
• Earlier programs structured as methods that call
one another in a disciplined, hierarchical manner
• Recursive methods
– Call themselves
– Useful for some problems to define a method to call itself
– Can be called directly or indirectly through another
method
 2005 Pearson Education, Inc. All rights reserved.
6
Chapter
Recursion examples and exercises in this book
15
Factorial Method (Fig. 15.3 and Fig. 15.4)
Fibonacci Method (Fig. 15.5 and Fig. 15.6)
String Permutations (Fig. 15.12 and Fig. 15.13)
Towers of Hanoi (Fig. 15.15 and Fig. 15.16)
Fractals (Fig. 15.23 and Fig. 15.24)
What Does This Code Do? (Exercise 15.7, Exercise 15.12 and Exercise 15.13)
Find the Error in the Following Code (Exercise 15.8)
Raising an Integer to an Integer Power (Exercise 15.9)
Visualizing Recursion (Exercise 15.10)
Greatest Common Divisor (Exercise 15.11)
Determine Whether a String Is a Palindrome (Exercise 15.14)
Eight Queens (Exercise 15.15)
Print an Array (Exercise 15.16)
Print an Array Backward (Exercise 15.17)
Minimum Value in an Array (Exercise 15.18)
Star Fractal (Exercise 15.19)
Maze Traversal Using Recursive Backtracking (Exercise 15.20)
Generating Mazes Randomly (Exercise 15.21)
Mazes of Any Size (Exercise 15.22)
Time Needed to Calculate a Fibonacci Number (Exercise 15.23)
Fig. 15.1 | Summary of the 32 recursion examples and exercises in this text.
(Part 1 of 2)
 2005 Pearson Education, Inc. All rights reserved.
7
Chapter
Recursion examples and exercises in this book
16
Merge Sort (Fig. 16.10 and Fig. 16.11)
Linear Search (Exercise 16.8)
Binary Search (Exercise 16.9)
Quicksort (Exercise 16.10)
17
Binary-Tree Insert (Fig. 17.17)
Preorder Traversal of a Binary Tree (Fig. 17.17)
Inorder Traversal of a Binary Tree (Fig. 17.17)
Postorder Traversal of a Binary Tree (Fig. 17.17)
Print a Linked List Backward (Exercise 17.20)
Search a Linked List (Exercise 17.21)
Fig. 15.1 | Summary of the 32 recursion examples and exercises in this text.
(Part 2 of 2)
 2005 Pearson Education, Inc. All rights reserved.
8
15.2 Recursion Concepts
• Recursive problem-solving elements
– Base case
• Recursive method capable of solving only simplest case—the base case
• If method is called with base case, method returns result
– If method is called with more complex problem, problem divided into
two pieces—a piece the method knows how to do and a piece the method
does not know how to do (called recursive call or recursion step)
– Recursive call/recursion step
• Must resemble original problem but be slightly simpler or smaller version
• Method calls fresh copy of itself to work on smaller problem
• Normally includes return statement
• Indirect recursion
– Recursive method calls another method that eventually makes call back
to recursive method
 2005 Pearson Education, Inc. All rights reserved.
9
15.3 Example Using Recursion:
Factorials
• Factorial of n, or n! is the product
n · (n – 1) · (n – 2) · … · 1
With 1! equal to 1 and 0! Defined to be 1.
• Can be solved recursively or iteratively (nonrecursively)
• Recursive solution uses following relationship:
n! = n · (n – 1)!
• Infinite recursion – recursive calls are continuously made
until memory has been exhausted
– Caused by either omitting base case or writing recursion step
that does not converge on base case
 2005 Pearson Education, Inc. All rights reserved.
10
Fig. 15.2 | Recursive evaluation of 5!.
 2005 Pearson Education, Inc. All rights reserved.
1
// Fig. 15.3: FactorialCalculator.java
2
// Recursive factorial method.
11
Outline
3
4
public class FactorialCalculator
5
{
6
// recursive method factorial
7
8
public long factorial( long number )
{
Factorial
Base case returns 1 Calculator.java
9
if ( number <= 1 ) // test for base case
10
11
return 1; // base cases: 0! = 1 and 1! = 1
Recursion
else // recursion step
12
13
14
return number * factorial( number - 1 );
} // end method factorial
15
16
// output factorials for valuesPortion
0-10
public void displayFactorials()
17
18
{
19
20
21
step breaks problem into two parts: one the
method knows how to do, one the method does not
methodRecursive
knows how
call:
to Portion
do
method does not know how to
do; smaller version of original problem
// calculate the factorials of 0 through 10
for ( int counter = 0; counter <= 10; counter++ )
System.out.printf( "%d! = %d\n", counter, factorial( counter ) );
} // end method displayFactorials
22 } // end class FactorialCalculator
Original call to recursive method
 2005 Pearson Education,
Inc. All rights reserved.
12
Common Programming Error 15.1
Either omitting the base case or writing the
recursion step incorrectly so that it does not
converge on the base case can cause a logic error
known as infinite recursion, where recursive calls
are continuously made until memory has been
exhausted. This error is analogous to the problem
of an infinite loop in an iterative (nonrecursive)
solution.
 2005 Pearson Education, Inc. All rights reserved.
1
// Fig. 15.4: FactorialTest.java
2
// Testing the recursive factorial method.
13
Outline
3
4
public class FactorialTest
5
{
6
// calculate factorials of 0-10
7
public static void main( String args[] )
8
{
FactorialTest.java
Calculate and display factorials
9
FactorialCalculator factorialCalculator = new FactorialCalculator();
10
factorialCalculator.displayFactorials();
11
} // end main
12 } // end class FactorialTest
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
 2005 Pearson Education,
Inc. All rights reserved.
14
15.4 Example Using Recursion:
Fibonacci Series
• Fibonacci series begins with 0 and 1 and has property that
each subsequent Fibonacci number is the sum of previous
two Fibonacci numbers.
• Series occurs in nature, ratio of successive Fibonacci
numbers converges on golden ratio or golden mean
• Fibonacci series defined recursively as:
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)
• Recursive solution for calculating Fibonacci values results
in explosion of recursive method calls
 2005 Pearson Education, Inc. All rights reserved.
1
// Fig. 15.5: FibonacciCalculator.java
2
// Recursive fibonacci method.
15
Outline
3
4
public class FibonacciCalculator
5
{
6
// recursive declaration of method fibonacci
7
public long fibonacci( long number )
8
9
{
10
11
Two base cases
if ( ( number == 0 ) || ( number == 1 ) ) // base cases
return number;
return fibonacci( number - 1 ) + fibonacci( number - 2 );
} // end method fibonacci
15
16
public void displayFibonacci()
{
19
Calculator.java
Two recursive calls
else // recursion step
12
13
14
17
18
Fibonacci
for ( int counter = 0; counter <= 10; counter++ )
System.out.printf( "Fibonacci of %d is: %d\n", counter,
fibonacci( counter ) );
20
} // end method displayFibonacci
21 } // end class FibonacciCalculator
Original call to recursive method
 2005 Pearson Education,
Inc. All rights reserved.
1
// Fig. 15.6: FibonacciTest.java
2
// Testing the recursive fibonacci method.
16
Outline
3
4
public class FibonacciTest
5
{
6
public static void main( String args[] )
7
{
8
Calculate and display
FibonacciCalculator fibonacciCalculator = new FibonacciCalculator();
9
fibonacciCalculator.displayFibonacci();
10
FibonacciTest.java
Fibonacci values
} // end main
11 } // end class FibonacciTest
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
of
of
of
of
of
of
of
of
of
of
of
0 is: 0
1 is: 1
2 is: 1
3 is: 2
4 is: 3
5 is: 5
6 is: 8
7 is: 13
8 is: 21
9 is: 34
10 is: 55
 2005 Pearson Education,
Inc. All rights reserved.
17
Fig. 15.7 | Set of recursive calls for fibonacci( 3 ).
 2005 Pearson Education, Inc. All rights reserved.
18
Performance Tip 15.1
Avoid Fibonacci-style recursive programs,
because they result in an exponential
“explosion” of method calls.
 2005 Pearson Education, Inc. All rights reserved.
19
15.5 Recursion and the Method Call
Stack
• Method call stack used to keep track of method
calls and local variables within a method call
• Just as with nonrecursive programming,
recursive method calls are placed at the top of the
method call stack
• As recursive method calls return, their activation
records are popped off the stack and the previous
recursive calls continue executing
• Current method executing is always method
whose activation record is at top of stack
 2005 Pearson Education, Inc. All rights reserved.
20
Fig. 15.8 | Method calls made within the call fibonacci( 3 ).
 2005 Pearson Education, Inc. All rights reserved.
21
Fig. 15.9 | Method calls on the program execution stack.
 2005 Pearson Education, Inc. All rights reserved.
22
15.6 Recursion vs. Iteration
• Any problem that can be solved recursively can be solved
iteratively
• Both iteration and recursion use a control statement
– Iteration uses a repetition statement
– Recursion uses a selection statement
• Iteration and recursion both involve a termination test
– Iteration terminates when the loop-continuation condition fails
– Recursion terminates when a base case is reached
• Recursion can be expensive in terms of processor time and
memory space, but usually provides a more intuitive
solution
 2005 Pearson Education, Inc. All rights reserved.
23
Software Engineering Observation 15.1
Any problem that can be solved recursively can
also be solved iteratively (nonrecursively). A
recursive approach is normally preferred over an
iterative approach when the recursive approach
more naturally mirrors the problem and results in
a program that is easier to understand and debug.
A recursive approach can often be implemented
with fewer lines of code. Another reason to choose a
recursive approach is that an iterative one might
not be apparent.
 2005 Pearson Education, Inc. All rights reserved.
1
// Fig. 15.10: FactorialCalculator.java
2
// Iterative factorial method.
24
Outline
3
4
public class FactorialCalculator
5
6
{
// recursive declaration of method factorial
7
public long factorial( long number )
8
{
9
// iterative declaration of method factorial
for ( long i = number; i >= 1; i-- )
result *= i;
} // end method factorial
18
// output factorials for values 0-10
19
20
public void displayFactorials()
{
23
24
Iterative solution uses counter-controlled repetition
return result;
16
17
21
22
Calculator.java
long result = 1;
10
11
12
13
14
15
Factorial
// calculate the factorials of 0 through 10
for ( int counter = 0; counter <= 10; counter++ )
System.out.printf( "%d! = %d\n", counter, factorial( counter ) );
} // end method displayFactorials
25 } // end class FactorialCalculator
 2005 Pearson Education,
Inc. All rights reserved.
1
// Fig. 15.11: FactorialTest.java
2
// Testing the iterative factorial method.
25
Outline
3
4
public class FactorialTest
5
{
6
// calculate factorials of 0-10
7
public static void main( String args[] )
8
{
9
FactorialCalculator factorialCalculator = new FactorialCalculator();
10
factorialCalculator.displayFactorials();
11
FactorialTest.java
} // end main
12 } // end class FactorialTest
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
 2005 Pearson Education,
Inc. All rights reserved.
26
Performance Tip 15.2
Avoid using recursion in situations requiring
high performance. Recursive calls take time
and consume additional memory.
 2005 Pearson Education, Inc. All rights reserved.
27
Common Programming Error 15.2
Accidentally having a nonrecursive method call
itself either directly or indirectly through another
method can cause infinite recursion.
 2005 Pearson Education, Inc. All rights reserved.
28
15.7 String Permutations
• Permutations of a string of text – all the different strings
that can be created by rearranging characters of original
string
• Words created from permutations are known as
anagrams
• Recursive solution: Remove one character, find
permutations of remaining characters (recursive case),
combine permutations with character that was removed
• Base case: Finding permutations for just one character –
character itself is the only permutation
• Any string provides n! permutations for n characters
 2005 Pearson Education, Inc. All rights reserved.
1
// Fig. 15.12: Permutation.java
2
// Recursive method to find all permutations of a String.
29
3
4
5
Outline
public class Permutation
{
6
// recursive declaration of method permuteString
7
8
private void permuteString(
String beginningString, String endingString )
9
{
Permutation.java
Base case: Combine removed characters
(1 of 2)with
beginningString
endingString, which is only one character
10
// base case: if string to permute is length less than or equal
to
(beginningString)
11
12
// 1, just display this string concatenated with
if ( endingString.length() <= 1 )
13
14
15
System.out.println( beginningString + endingString );
else // recursion step: permute endingString
{
16
17
// for each character in endingString
for ( int i = 0; i < endingString.length(); i++ )
18
19
20
{
try
{
Remove one character; We will find
eliminatingpermutations
the
for remaining characters
21
22
// create new string to permute by
// character at index i
23
24
String newString = endingString.substring( 0, i ) +
endingString.substring( i + 1 );
25
 2005 Pearson Education,
Inc. All rights reserved.
26
// recursive call with a new string to permute
27
// and a beginning string to concatenate, which
28
// includes the character at index i
29
permuteString( beginningString +
endingString.charAt( i ), newString );
30
Outlinefor
Recursive call: find permutations
remaining characters then reattach
removed characters
31
} // end try
32
catch ( StringIndexOutOfBoundsException exception )
33
{
34
35
36
37
38
exception.printStackTrace();
} // end catch
30
Permutation.java
(2 of 2)
} // end for
} // end else
} // end method permuteString
39 } // end class Permutation
 2005 Pearson Education,
Inc. All rights reserved.
1
// Fig. 15.13: PermutationTest.java
2
// Testing the recursive method to permute strings.
3
4
5
import java.util.Scanner;
6
7
8
9
{
31
Outline
public class PermutationTest
PermutationTest
.java
public static void main( String args[] )
{
Scanner scanner = new Scanner( System.in );
10
11
12
Permutation permutationObject = new Permutation();
13
14
15
16
String input = scanner.nextLine(); // retrieve String to permute
(1 of 2)
System.out.print( "Enter a string: " );
// permute String
permutationObject.permuteString( "", input );
17
} // end main
18 } // end class PermutationTest
Initial call to recursive method; There
are no removed characters yet, so
first argument is “”
 2005 Pearson Education,
Inc. All rights reserved.
math
maht
mtah
mtha
mhat
mhta
amth
amht
atmh
athm
ahmt
ahtm
tmah
tmha
tamh
tahm
thma
tham
hmat
hmta
hamt
hatm
htma
htam
32
Outline
PermutationTest
.java
(2 of 2)
 2005 Pearson Education,
Inc. All rights reserved.
33
15.8 Towers of Hanoi
• Classic problem – Priests in Far East are attempting to
move a stack of disks from one peg to another. One disk
must be moved at a time, at no time may a larger disk be
placed above a smaller disk
• Recursive solution:
– Move n – 1 disks from peg 1 to peg 2, using peg 3 as temporary
holding area
– Move the last disk (the largest) from peg 1 to peg 3
– Move the n – 1 disks from peg 2 to peg 3, using peg 1 as a
temporary holding area
• Base case: When only one disk needs to be moved – no
temporary holding area needed, disk is simply moved
 2005 Pearson Education, Inc. All rights reserved.
34
Fig. 15.14 | Towers of Hanoi for the case with four disks.
 2005 Pearson Education, Inc. All rights reserved.
1
// Fig. 15.15: TowersOfHanoi.java
2
3
// Program solves the towers of Hanoi problem, and
// demonstrates recursion.
4
5
public class TowersOfHanoi
6
{
7
int numDisks; // number of disks to move
8
9
public TowersOfHanoi( int disks )
10
11
{
12
13
14
15
16
} // end TowersOfHanoi constructor
17
18
{
19
20
35
Outline
TowersOfHanoi.java
(1 of 2)
numDisks = disks;
// recusively move disks through towers
public void solveTowers( int disks, int sourcePeg, int destinationPeg,
int tempPeg )
// base case -- only one disk to move
if ( disks == 1 )
{
Base case: Simply display move
21
System.out.printf( "\n%d --> %d", sourcePeg, destinationPeg );
22
return;
23
24
} // end if
 2005 Pearson Education,
Inc. All rights reserved.
25
// recursion step -- move disk to tempPeg, then to destinationPeg
26
// move ( disks - 1 ) disks from sourcePeg to tempPeg recursively
27
solveTowers( disks - 1, sourcePeg, tempPeg, destinationPeg );
28
36
Outline
Move last disk from peg 1 to peg 3
29
// move last disk from sourcePeg to destinationPeg
30
Move
n-1 disks from
peg peg
1 to 3peg
as TowersOfHanoi.java
temporary
2
System.out.printf( "\n%d --> %d", sourcePeg,
destinationPeg
); Use
holding area
31
32
// move ( disks - 1 ) disks from tempPeg to destinationPeg
33
solveTowers( disks - 1, tempPeg, destinationPeg, sourcePeg );
34
} // end method solveTowers
(2 of 2)
35 } // end class TowersOfHanoi
as temporary
Move n-1 disks from Use
peg peg
2 to 1peg
3
holding area
 2005 Pearson Education,
Inc. All rights reserved.
1
// Fig. 15.16: TowersOfHanoiTest.java
2
// Test the solution to the Towers of Hanoi problem.
37
Outline
3
4
public class TowersOfHanoiTest
5
{
public static void main( String args[] )
{
6
7
TowersOfHanoiTest
8
9
int startPeg = 1;
int endPeg = 3;
// value 1 used to indicate startPeg in output
// value 3 used to indicate endPeg in output
10
11
int tempPeg = 2;
// value 2 used to indicate tempPeg in output
int totalDisks = 3; // number of disks
12
13
14
TowersOfHanoi towersOfHanoi = new TowersOfHanoi( totalDisks );
15
towersOfHanoi.solveTowers( totalDisks, startPeg, endPeg, tempPeg );
// initial nonrecursive call: move all disks.
.java
Make initial call to recursive method
16
} // end main
17 } // end class TowersOfHanoiTest
1
1
3
1
2
2
1
-->
-->
-->
-->
-->
-->
-->
3
2
2
3
1
3
3
 2005 Pearson Education,
Inc. All rights reserved.
38
15.9 Fractals
• Fractal – a geometric figure that often can be
generated from a pattern repeated recursively an
infinite number of times
• Pattern applied to each segment of original figure
• Benoit Mandelbrot introduced term “fractal,”
along with specifics of how fractals are created
and their practical applications
– Help us better understand patterns in nature, the human
body and the universe
– Popular art form
 2005 Pearson Education, Inc. All rights reserved.
39
15.9 Fractals
• Self-similar property – fractals have this property
in the case that, when subdivided into parts, each
resembles a reduced-size copy of the whole
• If part is exact copy of original, fractal is said to
be strictly self similar
• Each time pattern is applied, fractal is said to be
at new level or depth
• Fractal examples: Koch Curve, Koch Snowflake
 2005 Pearson Education, Inc. All rights reserved.
(a)
(b)
(c)
(d)
(e)
(f)
40
Fig. 15.17 | Koch Curve fractal.
 2005 Pearson Education, Inc. All rights reserved.
41
Fig. 15.18’ | “Lo fractal” at level 0.
 2005 Pearson Education, Inc. All rights reserved.
42
Fig. 15.19 | Determining points C and D for level 1 of “Lo fractal.”
 2005 Pearson Education, Inc. All rights reserved.
43
Fig. 15.20 | “Lo fractal” at level 1, with C and D points determined for level 2. [Note: The fractal at level
0 is included as a dashed line as a reminder of where the line was located in relation to the current
fractal.]
 2005 Pearson Education, Inc. All rights reserved.
44
Fig. 15.21 | “Lo fractal” at level 2, with dashed lines from level 1 provided.
 2005 Pearson Education, Inc. All rights reserved.
45
Fig. 15.22 | “Lo fractal” at level 2.
 2005 Pearson Education, Inc. All rights reserved.
1
// Fig. 15.23: Fractal.java
2
// Demonstrates user interface for drawing a fractal.
3
import java.awt.Color;
4
5
import java.awt.FlowLayout;
import java.awt.event.ActionEvent;
6
import java.awt.event.ActionListener;
7
import javax.swing.JFrame;
8
9
import javax.swing.JButton;
import javax.swing.JLabel;
10 import javax.swing.JPanel;
11 import javax.swing.JColorChooser;
12
13 public class Fractal extends JFrame
14 {
15
private final int WIDTH = 400; // define width of GUI
16
private final int HEIGHT = 480; // define height of GUI
17
18
19
20
Outline
Fractal.java
(1 of 5)
private final int MIN_LEVEL = 0;
private Color color = Color.BLUE;
private JButton changeColorJButton, increaseLevelJButton,
decreaseLevelJButton;
21
22
23
private JLabel levelJLabel;
private FractalJPanel drawSpace;
24
25
private JPanel mainJPanel, controlJPanel;
26
27
// set up GUI
public Fractal()
28
{
29
30
46
super( "Fractal" );
 2005 Pearson Education,
Inc. All rights reserved.
31
// set up control panel
32
33
controlJPanel = new JPanel();
controlJPanel.setLayout( new FlowLayout() );
34
35
36
// set up color button and register listener
changeColorJButton = new JButton( "Color" );
37
38
controlJPanel.add( changeColorJButton );
changeColorJButton.addActionListener(
39
40
new ActionListener() // anonymous inner class
{
41
42
43
44
45
// process changeColorJButton event
public void actionPerformed( ActionEvent event )
{
color = JColorChooser.showDialog(
Fractal.this, "Choose a color", color );
46
47
// set default color, if no color is returned
48
49
50
51
52
53
54
47
Outline
Fractal.java
(2 of 5)
if ( color == null )
color = Color.BLUE;
drawSpace.setColor( color );
} // end method actionPerformed
} // end anonymous inner class
); // end addActionListener
55
 2005 Pearson Education,
Inc. All rights reserved.
56
// set up decrease level button to add to control panel and
57
58
// register listener
decreaseLevelJButton = new JButton( "Decrease Level" );
59
controlJPanel.add( decreaseLevelJButton );
60
decreaseLevelJButton.addActionListener(
61
new ActionListener() // anonymous inner class
62
{
63
// process decreaseLevelJButton event
64
public void actionPerformed( ActionEvent event )
65
66
{
67
68
69
70
71
int level = drawSpace.getLevel();
// modify level if possible
if ( level >= MIN_LEVEL )
{
levelJLabel.setText( "Level: " + level );
drawSpace.setLevel( level );
74
repaint();
76
77
78
79
Outline
Fractal.java
Retrieve current level
Decrease level (3 of 5)
level--; // decrease level by one
72
73
75
48
Set new level
} // end if
} // end method actionPerformed
} // end anonymous inner class
Redraw fractal up to new level
); // end addActionListener
 2005 Pearson Education,
Inc. All rights reserved.
80
// set up increase level button to add to control panel
81
82
// and register listener
increaseLevelJButton = new JButton( "Increase Level" );
83
84
controlJPanel.add( increaseLevelJButton );
increaseLevelJButton.addActionListener(
85
86
87
88
89
90
public void actionPerformed( ActionEvent event )
{
int level = drawSpace.getLevel();
level++; // increase level by one
95
96
97
{
98
99
repaint();
} // end if
101
Outline
new ActionListener() // anonymous inner class
{
// process increaseLevelJButton event
91
92
93
94
100
49
Fractal.java
Retrieve current level
Increase level (4 of 5)
// modify level if possible
if ( level >= MIN_LEVEL )
levelJLabel.setText( "Level: " + level );
drawSpace.setLevel( level );
} // end method actionPerformed
} // end anonymous inner class
Set new level
Redraw fractal up to new level
102
103
); // end addActionListener
104
// set up levelJLabel to add to controlJPanel
105
106
levelJLabel = new JLabel( "Level: 0" );
controlJPanel.add( levelJLabel );
107
 2005 Pearson Education,
Inc. All rights reserved.
drawSpace = new FractalJPanel( 0 );
108
109
110
// create mainJPanel to contain controlJPanel and drawSpace
111
112
mainJPanel = new JPanel();
mainJPanel.add( controlJPanel );
113
mainJPanel.add( drawSpace );
114
50
Outline
Fractal.java
add( mainJPanel ); // add JPanel to JFrame
115
116
setSize( WIDTH, HEIGHT ); // set size of JFrame
117
118
119
setVisible( true ); // display JFrame
} // end Fractal constructor
120
121
public static void main( String args[] )
122
123
124
125
(5 of 5)
{
Fractal demo = new Fractal();
demo.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
} // end main
126 } // end class Fractal
 2005 Pearson Education,
Inc. All rights reserved.
1
// Fig. 15.24: FractalJPanel.java
2
// FractalJPanel demonstrates recursive drawing of a fractal.
3
import java.awt.Graphics;
4
5
6
import java.awt.Color;
import java.awt.Dimension;
import javax.swing.JPanel;
7
8
Outline
FractalJPanel.java
public class FractalJPanel extends JPanel
9 {
10
private Color color; // stores color used to draw fractal
11
12
private int level;
13
14
15
private final int WIDTH = 400; // defines width of JPanel
private final int HEIGHT = 400; // defines height of JPanel
16
// set the initial fractal level to the value specified
17
// and set up JPanel specifications
18
19
20
public FractalJPanel( int currentLevel )
{
color = Color.BLUE; // initialize drawing color to blue
// stores current level of fractal
21
level = currentLevel; // set initial fractal level
22
setBackground( Color.WHITE );
23
24
51
(1 of 6)
setPreferredSize( new Dimension( WIDTH, HEIGHT ) );
} // end FractalJPanel constructor
25
 2005 Pearson Education,
Inc. All rights reserved.
26
// draw fractal recursively
27
28
public void drawFractal( int level, int xA, int yA, int xB,
int yB, Graphics g )
29
{
52
Coordinates of first point for line
Coordinates
ofissecond
for line
where fractal
being point
applied
where fractalFractalJPanel.java
is being applied
Base case: Simply draw line, pattern is
next level
not applied
30
// base case: draw a line connecting two given points
31
if ( level == 0 )
32
33
34
g.drawLine( xA, yA, xB, yB );
else // recursion step: determine new points, draw
{
Outline
35
// calculate midpoint between (xA, yA) and (xB, yB)
36
37
int xC = ( xA
+ xB ) / step:
2; Apply
Recursion
int yC = ( yA + yB ) / 2;
38
39
// calculate the fourth point (xD, yD) which forms an
40
// isosceles right triangle between (xA, yA) and (xC, yC)
41
42
// where the right angle is at (xD, yD)
int xD = xA + ( xC - xA ) / 2 - ( yC - yA ) / 2;
43
44
int yD = yA + ( yC - yA ) / 2 + ( xC - xA ) / 2;
45
46
47
// recursively draw the Fractal
drawFractal( level - 1, xD, yD, xA, yA, g );
drawFractal( level - 1, xD, yD, xC, yC, g );
48
49
50
drawFractal( level - 1, xD, yD, xB, yB, g );
} // end else
} // end method drawFractal
fractal pattern
(2 of 6)
Calculate midpoint
Calculate point to form right
triangle
Apply pattern to three new lines
51
 2005 Pearson Education,
Inc. All rights reserved.
52
// start the drawing of fractal
53
public void paintComponent( Graphics g )
54
{
53
Outline
super.paintComponent( g );
55
56
57
// draw fractal pattern
58
59
g.setColor( color );
drawFractal( level, 100, 90, 290, 200, g );
60
} // end method paintComponent
61
62
// set the drawing color to c
63
public void setColor( Color c )
64
65
{
66
67
} // end method setColor
68
// set the new level of recursion
69
public void setLevel( int currentLevel )
70
{
Make first call to recursive method
FractalJPanel.java
whenever window is repainted
(3 of 6)
color = c;
71
level = currentLevel;
72
} // end method setLevel
73
 2005 Pearson Education,
Inc. All rights reserved.
74
75
// returns level of recursion
public int getLevel()
76
{
77
54
Outline
return level;
78
} // end method getLevel
79 } // end class FractalJPanel
FractalJPanel.java
(4 of 6)
 2005 Pearson Education,
Inc. All rights reserved.
55
Outline
FractalJPanel.java
(5 of 6)
 2005 Pearson Education,
Inc. All rights reserved.
56
Outline
FractalJPanel.java
(6 of 6)
 2005 Pearson Education,
Inc. All rights reserved.
57
15.10 Recursive Backtracking
• Recursive Backtracking – process of using
recursion to return to earlier decision point
• If one set of recursive calls does not result in
solution, program backs up to previous decision
point and makes different decision, often
resulting in another set of recursive calls
• Examples
– Maze problem
– Eight-Queens problem
 2005 Pearson Education, Inc. All rights reserved.