Chapter 16 Recursive Algorithms 2000 McGraw-Hl‖ Introduction to Object-Oriented Programming with Java-Wu Chapter 16-1
© 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16 - 1 Chapter 16 Recursive Algorithms
Chapter 16 objectives After you have read and studied this chapter, you should be able to e Write recursive algorithms for mathematical functions and nonnumerical operations e Decide when to use recursion and when not to e Describe the recursive quicksort algorithm and explain how its performance is better than selection and bubble sort algorithms C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 16-2
© 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
Recursion r The factorialof N is the product of the first N positive integers N*(N-1)*(N-2) r The factorial of N can be defined recursrvelyas factorial( n) n factorial( N-1) otherwise C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 16-3
© 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
Recursive method r An recursive method is a method that contains a statement (or statements) that makes a call to itself r Implementing the factorial of N recursively will result in the following method public int factorial( int N Test to stop or continue if(N==1){ End case return 1 recursion stops Recursive case recursion continues return N factorial( N-1)i C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 16-4
© 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
Directory Listing r 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()i//get the contents String dirPath getAbsolutePath( for (int i =0; i< fileList length 1++) File file new File( dirPath "\\" filelist[i] )i Tes if( file. isFile()( //it's a file End case h System. out. println( file. getName()) else i Recursive case directoryListing( file )i //it's a directory //so recurse C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 16-5
© 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