More generally, there is no guarantee that the size of the input for a recursive call brings us closer to a solution than the original input. Hence each recursive application of quick-sort consumes a strictly shorter list than the given one. Eventually, quick-sort receives and returns empty . Without such an argument an algorithm must be considered incomplete. A good termination argument may on occasion also reveal additional termination cases.
Figure summarizes the suggestions on the design of algorithms.
Read the table in conjunction with those of the preceding chapters. Define the function tabulate-div , which accepts a number n and tabulates the list of all of its divisors, starting with 1 and ending in n . In general, this function yields a list that is approximately half as long as the input. Make sure to develop the functions independently. The latter is the result.