Fundamentals of Python: From First Programs Through Data StructuresObjectivesObjectives (continued)n log n SortingOverview of QuicksortPartitioningComplexity Analysis of QuicksortSlide 8Implementation of QuicksortMerge SortMerge Sort (continued)Slide 12Slide 13Slide 14Complexity Analysis for Merge SortRecursive List ProcessingBasic Operations on a Lisp-Like ListBasic Operations on a Lisp-Like List (continued)Recursive Traversals of a Lisp-Like ListRecursive Traversals of a Lisp-Like List (continued)Building a Lisp-Like ListBuilding a Lisp-Like List (continued)Slide 23The Internal Structure of a Lisp-Like ListLists and Functional ProgrammingLists and Functional Programming (continued)Recursion and BacktrackingA General Recursive StrategyA General Recursive Strategy (continued)Slide 30The Maze Problem RevisitedSlide 32Slide 33The Eight Queens ProblemThe Eight Queens Problem (continued)Slide 36Slide 37Slide 38Recursive Descent and Programming LanguagesIntroduction to GrammarsIntroduction to Grammars (continued)Slide 42Slide 43Slide 44Recognizing, Parsing, and Interpreting Sentences in a LanguageLexical Analysis and the ScannerParsing StrategiesParsing Strategies (continued)Case Study: A Recursive Descent ParserSlide 50Case Study: A Recursive Descent Parser (continued)The Costs and Benefits of RecursionNo, Maybe, and YesGetting Rid of RecursionGetting Rid of Recursion (continued)Tail RecursionTail Recursion (continued)SummarySummary (continued)Fundamentals of Python:From First Programs Through Data Structures Chapter 17RecursionFundamentals of Python: From First Programs Through Data Structures 2ObjectivesAfter completing this chapter, you will be able to:•Explain how a recursive, divide-and-conquer strategy can be used to develop n log n sort algorithms•Develop recursive algorithms for processing recursive data structures•Use a recursive strategy to implement a backtracking algorithmFundamentals of Python: From First Programs Through Data Structures 3Objectives (continued)•Describe how recursion can be used in software that recognizes or parses sentences in a language•Recognize the performance trade-offs between recursive algorithms and iterative algorithmsFundamentals of Python: From First Programs Through Data Structures 4n log n Sorting•Sort algorithms you studied in Chapter 11 have O(n2) running times•Better sorting algorithms are O(n log n)–Use a divide-and-conquer strategyFundamentals of Python: From First Programs Through Data Structures 5Overview of Quicksort•Begin by selecting item at list’s midpoint (pivot)•Partition items in the list so that all items less than the pivot end up at the left of the pivot, and the rest end up to its right•Divide and conquer–Reapply process recursively to sublists formed by splitting list at pivot•Process terminates each time it encounters a sublist with fewer than two itemsFundamentals of Python: From First Programs Through Data Structures 6Partitioning•One way of partitioning the items in a sublist:–Interchange the pivot with the last item in the sublist–Establish a boundary between the items known to be less than the pivot and the rest of the items–Starting with first item in sublist, scan across sublist•When an item < pivot is encountered, swap it with first item after the boundary and advance the boundary–Finish by swapping the pivot with the first item after the boundaryFundamentals of Python: From First Programs Through Data Structures 7Complexity Analysis of Quicksort•Best-case performance: O(n log n)–When each time, the dividing line between the new sublists turns out to be as close to the center of the current sublist as possible•Worst-case performance: O(n2)  list is sorted•If implemented as a recursive algorithm, must also consider memory usage for the call stack–O(log n) in the best case and O(n) in the worst case•When choosing pivot, selecting a random position helps approximate O(n log n) performance in average caseFundamentals of Python: From First Programs Through Data Structures 8Complexity Analysis of Quicksort (continued)Fundamentals of Python: From First Programs Through Data Structures 9Implementation of Quicksort•The quicksort algorithm is most easily coded using a recursive approach•The following script defines:–A top-level quicksort function for the client–A recursive quicksortHelper function to hide the extra arguments for the end points of a sublist–A partition functionFundamentals of Python: From First Programs Through Data Structures 10Merge Sort•Employs a recursive, divide-and-conquer strategy to break the O(n2) barrier:–Compute the middle position of a list and recursively sort its left and right sublists (divide and conquer)–Merge sorted sublists back into a single sorted list–Stop when sublists can no longer be subdivided•Three functions collaborate in this strategy:–mergeSort–mergeSortHelper–mergeFundamentals of Python: From First Programs Through Data Structures 11Merge Sort (continued)Fundamentals of Python: From First Programs Through Data Structures 12Merge Sort (continued)Fundamentals of Python: From First Programs Through Data Structures 13Merge Sort (continued)Fundamentals of Python: From First Programs Through Data Structures 14Merge Sort (continued)Fundamentals of Python: From First Programs Through Data Structures 15Complexity Analysis for Merge Sort•Maximum running time is O(n log n) in all cases:–Running time of merge is dominated by two for statements; each loops (high - low + 1) times•Running time is O(high - low)•All the merges at a single level take O(n) time–mergeSortHelper splits sublists as evenly as possible at each level; number of levels is O(log n)•Space requirements depend on the list’s size:–O(log n) space is required on the call stack to support recursive calls–O(n) space is used by the copy bufferFundamentals of Python: From First Programs Through Data Structures 16Recursive List Processing•Lisp: General-purpose, symbolic information-processing language–Developed by computer scientist John McCarthy–Stands for list processing–Basic data structure is the list•A Lisp list is a recursive data structure–Lisp programs often consist of a set of recursive functions for processing lists•We explore recursive list processing by developing a variant of Lisp listsFundamentals of Python: From First Programs Through Data Structures 17Basic Operations on a Lisp-Like List•A Lisp-like