I will now give some simple examples of recursive algorithms. Even if you have seen them before, study them again, keeping the techniques and theory from Chapter 8 in mind. For each example, look for the key steps of the friend paradigm. What are the subinstances given to the friend? What is the size of an instance? Does it get smaller? How are the friend’s solutions combined to give your solution? What does the tree of stack frames look like? What is the time complexity of the algorithm?
The classic divide-and-conquer algorithms are merge sort and quick sort. They both have the following basic structure.
General Recursive Sorting Algorithm: