Bài giảng Chapter 15: Recursive Algorithms

Chapter 15Recursive Algorithms©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Chapter 15 ObjectivesAfter you have read and studied this chapter, you should be able toWrite 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.15.1 Basic Elements of RecursionA 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.15.1 Basic Elements of RecursionThese 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.15.2 Directory ListingRecursive 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.15.2 Directory ListingWe 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 = file.list();©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.15.2 Directory ListingFollowing is the complete directoryListing method (the argument of which is a File object that represents a directory):©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.15.2 Directory Listingpublic void directoryListing(File dir){ String[] fileList = dir.list(); //get the contents String dirPath = dir.getAbsolutePath(); for (int i=0; i= pivot){ end--; } if(start < end){ //found a smaller number number[start] = number[end];©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.15.5 Quicksort //now find a number larger than pivot //from the start while(start < end && number[start] <= pivot){ start++; } if(start < end){ //found a larger number number[end] = number[start]; } }} while (start < end); //done, move the pivot back to the array number[start] = pivot; return start;}©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.15.5 QuicksortIn the worst case, quicksort executes roughly the same number of comparisons as the selection sort and bubble sort.On average, we can expect a partition process to split the array into two roughly equal subarrays.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 15.7A hierarchy of partitioning an array into smaller and smaller arrays in the quicksort.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.15.5 QuicksortWhen the size of all subarrays becomes 1, the array is sorted.The total number of comparisons for sorting the whole array isK * NN = 2Klog2N = KKN = N log2N©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.15.6 When Not to Use RecursionRecursion does not always provide an efficient or natural way to express the solution to a problem.public int fibonacci(int N){ if (N == 0 )|| N ==1){ return 1; //end case }else{ //recursive case return fibonacci(N-1) + fibonacci(N-2); }}©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 15.8Recursive calls to compute fibonacci(5).©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.15.6 When Not to Use RecursionThis method is succinct and easy to understand, but it is very inefficient. A nonrecursive version is just as easy to understand.public int fibonacci(int N){ int fibN, fibN1, fibN2, cnt; if (N == 0 || N == 1){ return 1; }else{ fibN1 = fibN2 = 1; cnt = 2;©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.15.6 When Not to Use Recursion while (cnt <= N){ fibN = fibN1 + fibN2; //get the next Fib. no. fibN1 = fibN2; fibN2 = fibN; cnt++; } return fibN; }}©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.15.6 When Not to Use RecursionIn general, use recursion ifA recursive solution is natural and easy to understand.A recursive solution does not result in excessive duplicate computation.The equivalent iterative solution is too complex.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.