Making Choices

A user cannot distinguish sort and quick-sort. Both consume a list of numbers; both produce a list that consists of the same numbers arranged in ascending order. To an observer, the functions are completely equivalent. This raises the question of which of the two a programmer should provide. More generally, if we can develop a function using structural recursion and an equivalent one using generative recursion, what should we do? To understand this choice better, let's discuss another classical example of generative recursion from mathematics: the problem of finding the greatest common divisor of two positive natural numbers. All such numbers have at least one divisor in common: 1. On occasion, this is also the only common divisor. For example, 2 and 3 have only 1 as common divisor because 2 and 3, respectively, are the only other divisors. Then again, 6 and 25 are both numbers with several divisors:

1. 6 is evenly divisible by 1, 2, 3, and 6;
2. 25 is evenly divisible by 1, 5, and 25.

1. 18 is evenly divisible by 1, 2, 3, 6, and 9;
2. 24 is evenly divisible by 1, 2, 3, 4, 6, 8, and 12.

Following the design recipe, we start with a contract, a purpose statement, and a header:

;; gcd : N[>= 1] N[>= 1] -> N
;; to find the greatest common divisior of n and m 
(define (gcd n m) 
  ...) 

The contract specifies the precise inputs: natural numbers that are greater or equal to 1 (not 0).

Now we need to make a decision whether we want to pursue a design based on structural or on generative recursion. Since the answer is by no means obvious, we develop both. For the structural version, we must consider which input the function should process: n, m, or both. A moment's consideration suggests that what we really need is a function that starts with the smaller of the two and outputs the first number smaller or equal to this input that evenly divides both n and m.

;; gcd-structural : N[>= 1] N[>= 1] -> N ;; to find the greatest common divisior of n and m ;; structural recursion using data definition of N[>= 1] (define (gcd-structural n m) (local ((define (first-divisior-<= i) (cond [(= i 1) 1] [else (cond [(and (= (remainder n i) 0) (= (remainder m i) 0)) i] [else (first-divisior-<= (- i 1))])]))) (first-divisior-<= (min m n)))) Figure: Finding the greatest common divisor via structural recursion

We use local to define an appropriate auxiliary function: see figure . The conditions ``evenly divisible'' have been encoded as (= (remainder n i) 0) and (= (remainder m i) 0). The two ensure that i divides n and m without a remainder. Testing gcd-structural with the examples shows that it finds the expected answers.

Although the design of gcd-structural is rather straightforward, it is also naive. It simply tests for every number whether it divides both n and m evenly and returns the first such number. For small natural numbers, this process works just fine. Consider the following example, however:

(gcd-structural 101135853 45014640)

Exercise 26.3.1

Enter the definition of gcd-structural into the Definitions window and evaluate (time (gcd-structural 101135853 45014640)) in the Interactions window.

Hint: After testing gcd-structural conduct the performance tests in the Full Scheme language (without debugging), which evaluates expressions faster than the lower language levels but with less protection. Add (require-library ``core.ss'') to the top of the Definitions window. Have some reading handy! Solution

Since mathematicians recognized the inefficiency of the ``structural algorithm'' a long time ago, they studied the problem of finding divisiors in more depth. The essential insight is that for two natural numbers larger and smaller, their greatest common divisor is equal to the greatest common divisior of smaller and the remainder of larger divided into smaller. Here is how we can put this insight into equational form:

  (gcd larger smaller) 
= (gcd smaller (remainder larger smaller)) 

Here is how this insight applies to our small example:

1. The given numbers are 18 and 24.
2. According to the mathematicians' insight, they have the same greatest common divisor as 18 and 6.
3. And these two have the same greatest common divisor as 6 and 0.

Working through the example not only explains the idea but also suggests how to discover the case with a trivial solution. When the smaller of the two numbers is 0, the result is the larger number. Putting everything together, we get the following definition:

;; gcd-generative : N[>= 1] N[>=1] -> N
;; to find the greatest common divisior of n and m 
;; generative recursion: (gcd n m) = (gcd n (remainder m n)) if (<= m n) 
(define (gcd-generative n m) 
  (local ((define (clever-gcd larger smaller) 
            (cond 
              [(= smaller 0) larger] 
              [else (clever-gcd smaller (remainder larger smaller))]))) 
    (clever-gcd (max m n) (min m n)))) 

If we now use gcd-generative with our complex example from above:

(gcd-generative 101135853 45014640)

Formulate informal answers to the four key questions for gcd-generative. Solution

Exercise 26.3.3

Define gcd-generative and evaluate

(time (gcd-generative 101135853 45014640))

Evaluate (clever-gcd 101135853 45014640) by hand. Show only those lines that introduce a new recursive call to clever-gcd. Solution

Exercise 26.3.4

Formulate a termination argument for gcd-generative. Solution

Considering the above example, it is tempting to develop functions using generative recursion. After all, they produce answers faster! This judgment is too rash for three reasons. First, even a well-designed algorithm isn't always faster than an equivalent structurally recursive function. For example, quick-sort wins only for large lists; for small ones, the standard sort function is faster. Worse, a badly designed algorithm can wreck havoc on the performance of a program. Second, it is typically easier to design a function using the recipe for structural recursion. Conversely, designing an algorithm requires an idea of how to generate new, smaller problems, a step that often requires deep mathematical insight. Finally, people who read functions can easily understand structurally recursive functions, even without much documentation. To understand an algorithm, the generative step must be well explained, and even with a good explanation, it may still be difficult to grasp the idea.

Experience shows that most functions in a program employ structural recursion; only a few exploit generative recursion. When we encounter a situation where a design could use either the recipe for structural or generative recursion, the best approach is often to start with a structural version. If it turns out to be too slow, the alternative design using generative recursion should be explored. If it is chosen, it is important to document the problem generation with good examples and to give a good termination argument.

Evaluate

(quick-sort (list 10 6 8 9 14 12 3 11 14 16 2))

Evaluate

(quick-sort (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14))

Exercise 26.3.6

Add sort and quick-sort to the Definitionswindow. Test the functions and then explore how fast each works on various lists. The experiment should confirm the claim that the plain sort function wins (in many comparisons) over quick-sort for short lists and vice versa. Determine the cross-over point. Then build a sort-quick-sort function that behaves like quick-sort for large lists and switches over to the plain sort function for lists below the cross-over point.

Hints: (1) Use the ideas of exercise  to create test cases. (2) Develop create-tests, a function that creates large test cases randomly. Then evaluate

(define test-case (create-tests 10000))
(collect-garbage) 
(time (sort test-case)) 
(collect-garbage) 
(time (quick-sort test-case))