? 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16 - 1
Chapter 16
Recursive Algorithms
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16 - 2
Chapter 16 Objectives
After you have read and studied this chapter,you
should be able to
Write recursive algorithms for mathematical functions
and nonnumerical operations.
Decide when to use recursion and when not to.
Describe the recursive quicksort algorithm and explain
how its performance is better than selection and bubble
sort algorithms.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16 - 3
Recursion
The factorial of N is the product of the first N
positive integers:
N * (N – 1) * (N – 2 ) *,,,* 2 * 1
The factorial of N can be defined recursively as
1 if N = 1
factorial( N ) =
N * factorial( N-1 ) otherwise
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16 - 4
Recursive Method
An recursive method is a method that contains a
statement (or statements) that makes a call to itself.
Implementing the factorial of N recursively will result
in the following method.
public int factorial( int N )
{
if ( N == 1 ) {
return 1;
}
else {
return N * factorial( N-1 );
}
}
Test to stop or
continue.
Recursive case,
recursion continues.
End case,
recursion stops.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16 - 5
Directory Listing
Here’s a sample recursive method for nonnumerical application,
The routine lists the names of all files in a given directory and
its subdirectories.
public void directoryListing( File dir )
{
//assumption,dir represents a directory
String[] fileList = dir.list(); //get the contents
String dirPath = dir.getAbsolutePath();
for (int i = 0; i < fileList.length; i++) {
File file = new File( dirPath + "\\" + fileList[i] );
if ( file.isFile() ) { //it’s a file
System.out.println( file.getName() );
}
else {
directoryListing( file ); //it’s a directory
} //so recurse
}
}
Recursive case
End case
Test
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16 - 6
Anagram
Here’s the second sample recursive method for nonnumerical
application,The routine lists all anagrams of a given word.
Word C A T
C T A
A T C
A C T
T C A
T A C
Anagrams
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16 - 7
Anagram Solution,Rotate and Recurse
The basic idea is to recurse on a sub-word after
every rotation,Here’s how:
C A T Recursion
A T C
T C A
Recursion
Recursion
Rotate Left
Rotate Left
C A T
C T A
A T C
A C T
T C A
T A C
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16 - 8
Anagram Method
public void anagram( String prefix,String suffix )
{
String newPrefix,newSuffix;
int numOfChars = suffix.length();
if (numOfChars == 1) {
//End case,print out one anagram
outputBox.printLine( prefix + suffix );
}
else {
for (int i = 1; i <= numOfChars; i++ ) {
newSuffix = suffix.substring(1,numOfChars);
newPrefix = prefix + suffix.charAt(0);
anagram( newPrefix,newSuffix ); //recursion
//rotate left to create a rearranged suffix
suffix = newSuffix + suffix.charAt(0);
}
}
}
End case
Test
Recursive case
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16 - 9
HiLo Game – Development Steps
1,Start with a program skeleton,Define the HiLoMain and
HiLo classes.
2,Add code to the HiLo class to play a game using a
dummy secret number.
3,Add code to the HiLo class to generate a random
number.
4,Finalize the code by removing temporary statements
and tying up loose ends.
The End