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
Anagram r Here's the second sample recursive method for nonnumerical application, The routine lists all anagrams of a given word Word CAT CTA ATC ACT Anagrams TCA TAC C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 16-6
© 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
Anagram Solution Rotate and recurse r The basic idea is to recurse on a sub-word after every rotation. Here's how CAT CAT Recursion CTA Rotate Left ATC A Recursion ACT Rotate Left ICA TCA excursion TAC C 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16-7
© 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
Anagram Method public void anagram( String prefix, String suffix String newPrefix, new Suffix Test int numofChars suffix length() if(numofChars 1){ End case //End case: print out one anagram outputBox. printLine( prefix suffix )i else f for (int i = l; i < numofChars; i++)I newSuffix suffix substring(l, numofChars)i newPrefix prefix suffix charAt (0) Recursive case anagram( newPrefix, newSuffix )i //recursion //rotate left to create a rearranged suffix suffix newSuffix suffix charAt(0)i C 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 16-8
© 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
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 C 2000 McGraw-Hill troduction to Object-Oriented Programming with Java--Wu Chapter 16-9
© 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
