Termination

Unfortunately, the standard recipe is not good enough for the design of algorithms. Up to now, a function has always produced an output for any legitimate input. That is, the evaluation has always stopped. After all, by the nature of our recipe, each natural recursion consumes an immediate piece of the input, not the input itself. Because data is constructed in a hierarchical manner, this means that the input shrinks at every stage. Hence the function sooner or later consumes an atomic piece of data and stops.

With functions based on generative recursion, this is no longer true. The internal recursions don't consume an immediate component of the input but some new piece of data, which is generated from the input. As exercise  shows, this step may produce the input over and over again and thus prevent the evaluation from ever producing a result. We say that the program LOOPS or is in an INFINITE LOOP.

In addition, even the slightest mistake in translating the process description into a function definition may cause an infinite loop. The problem is most easily understood with an example. Consider the following definition of smaller-items, one of the two ``problem generators'' for quick-sort:

;; smaller-items : (listof number) number -> (listof number)
;; to create a list with all those numbers on alon  
;; that are smaller than or equal to threshold 
(define (smaller-items alon threshold) 
  (cond 
    [(empty? alon) empty] 
    [else (if (<= (first alon) threshold) 
              (cons (first alon) (smaller-items (rest alon) threshold)) 
              (smaller-items (rest alon) threshold))])) 

Worse, if the quick-sort function from figure  is combined with this new version of smaller-items, it doesn't produce any output for (list 5):

  (quick-sort (list 5))
= (append (quick-sort (smaller-items 5 (list 5))) 
          (list 5) 
          (quick-sort (larger-items 5 (list 5)))) 
= (append    
          (list 5) 
          (quick-sort (larger-items 5 (list 5)))) 

The figure is not yet translated into HTML. Figure: Designing algorithms

The lesson from this example is that the design of algorithms requires one more step in our design recipe: a TERMINATION ARGUMENT, which explains why the process produces an output for every input and how the function implements this idea; or a warning, which explains when the process may not terminate. For quick-sort, the argument might look like this:

At each step, quick-sort partitions the list into two sublists using smaller-items and larger-items. Each function produces a list that is smaller than the input (the second argument), even if the threshold (the first argument) is an item on the list. Hence each recursive application of quick-sort consumes a strictly shorter list than the given one. Eventually, quick-sort receives and returns empty.

A good termination argument may on occasion also reveal additional termination cases. For example, (smaller-items N (list N)) and (larger-items N (list N)) always produce empty for any N. Therefore we know that quick-sort's answer for (list N) is (list N). To add this knowledge to quick-sort, we simply add a cond-clause:

(define (quick-sort alon)
  (cond 
    [(empty? alon) empty] 
    [(empty? (rest alon)) alon] 
    [else (append 
            (quick-sort (smaller-items alon (first alon))) 
            (list (first alon)) 
            (quick-sort (larger-items alon (first alon))))])) 

Figure  summarizes the suggestions on the design of algorithms. The dots indicate that the design of an algorith requires a new step: the termination argument. Read the table in conjunction with those of the preceding chapters.

Exercise 26.1.1

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. A number d is a divisior of a number n if the remainder of dividing n by d is 0, that is, (= (remainder n d) 0) is true. The smallest divisior of any number is 1; the largest one is the number itself. Solution

Exercise 26.1.2

Develop the function merge-sort, which sorts a list of numbers in ascending order, using the following two auxiliary functions:

1. The first one, make-singles, constructs a list of one-item lists from the given list of numbers. For example,

   (equal? (make-singles (list 2 5 9 3))
           (list (list 2) (list 5) (list 9) (list 3))) 
   

2. The second one, merge-all-neighbors, merges pairs of neighboring lists. More specifically, it consumes a list of lists (of numbers) and merges neighbors. For example,

   (equal? (merge-all-neighbors (list (list 2) (list 5) (list 9) (list 3)))
           (list (list 2 5) (list 3 9)))
   
   (equal? (merge-all-neighbors (list (list 2 5) (list 3 9))) 
           (list (list 2 3 5 9))) 
   

   In general, this function yields a list that is approximately half as long as the input. Why is the output not always half as long as the input?

The function merge-sort first uses make-singles to create a list of single lists; then it relies on merge-all-neighbors to shorten the list of lists until it contains a single list. The latter is the result. Solution