We will present several nonnumerical recursive algorithms in this chapter. We will also discuss some criteria for deciding when to use recursion and when not to. All the recursive algorithms we provide in this chapter, other than those we use for explanation, are algorithms that should be written recursively. | Chapter 15 Recursive Algorithms Chapter 15 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 that of selection and bubble sort algorithms. ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display. Basic Elements of Recursion A recursive method is a method that contains a statement that makes a call to itself. Any recursive method will include the following three basic elements: A test to stop or continue the recursion. An end case that terminates the recursion. A recursive call that continues the recursion. ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display. Basic Elements of Recursion These three elements are included in the following recursive factorial method: public int factorial(int N) { if (N == 1){ return 1; } else { return N* factorial(N-1); } } ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display. Directory Listing Recursive algorithms may be used for nonnumerical applications. This example of a recursive algorithm will list the file names of all files in a given directory of a hard disk and its subdirectories. ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display. Directory Listing We create a new File object by passing the name of a file or a directory: File file = new File(“D:/Java/Projects”); To get an array of names of files and subdirectories, we use the list method. String[] fileList = (); ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display. Directory Listing Following is the complete directoryListing method (the argument of which is a File object that represents a directory): ©TheMcGraw-Hill Companies, Inc. Permission required for . | Chapter 15 Recursive Algorithms Chapter 15 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 that of selection and bubble sort algorithms. ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display. Basic Elements of Recursion A recursive method is a method that contains a statement that makes a call to itself. Any recursive method will include the following three basic elements: A test to stop or continue the recursion. An end case that terminates the recursion. A recursive call that continues the recursion. ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display. Basic Elements of Recursion These three elements are included in the following recursive factorial method: public int .
