COMP 210 Lab 10: Generative Recursion

Today we look at some examples of generative recursion that illustrate important aspects of what we need to think about.

Design recipe, Integration example, GCD example, Ackerman's function example

Generative Recursion Design Recipe Review

In class, we concluded that we now have a new methodology for use with generative recursion. If a function is generative recursive, we modify our design recipe with the following changes:

When making function examples, we need even more examples, as they help us to find the algorithm we will use.
When making a template, we don't follow the structure of the data. Instead, we ask ourselves six questions:
- What is (are) the trivial case(s)?
- How do we solve the trivial case(s)?
- For the non-trivial case(s), how many subproblems do we use?
- How do we generate these subproblems?
- Do we combine the results of these subproblems?
- How do we combine the results of these subproblems?
We use the answers to fill in the following very general template:
```
     (define (f args …)
        (cond [(trivial? args …)
               (solve-trivial args …)]
              [else
               (combine (f (generate-subproblem1 args …) …)
                        …
                        (f (generate-subproblemn args …) …))]))
     
```
We add a step to reason about why our algorithm terminates, since this is no longer provided by simply following the structure of the data.

Integration example

One common mathematical problem is to find the area under some function f between some points xlo and xhi. I.e., given f, its integral is the area of the shape between f's curve and the x-axis. The integral can be solved symbolically, as in a standard calculus course. Alternatively, it can be solved numerically, given specific values of xlo and xhi.

Given f, the area can be calculated as follows:

	area under `f` from `xlo` to the `x`-midpoint
+	area under `f` from the `x`-midpoint to `xhi`

=	area under `f` from `xlo` to `xhi`

That seems obvious, but when do we stop using such a recurrence and actually calculate something? If xlo and xhi are "close enough", we can stop and approximate the shape under the curve. A rectangle or a trapezoid are each good and simple approximations. One simple definition of "close enough" is some fixed x-distance threshold, e.g., .001.

Integration exercises
Develop the program ; integrate : (num -> num) num num num -> num (define (integrate f xlo xhi threshold) …) that follows the above idea. Follow our methodology for developing generative recursive programs. Don't forget to make and use a good set of examples, although you might have difficulty calculating the result values of examples. Note that since this function works on general numbers, and numbers are not defined recursively, it is not clear how to use visitors with them. So, don't attempt to put your function in visitor-style. Discuss: What are some other approaches for determining when to stop the recursion (i.e., what is "close enough")? Discuss/Ponder: Instead of recurring on halves of the `x`-interval, what other approaches might you take? Discuss/Ponder: How could we generalize our algorithm? E.g., how could we use a function that computes the base case approximation, using a rectangular, trapezoidal, or whatever other approximation we might want? E.g., how could we use a function that generates a set of new intervals to recur on, given the current interval (`xlo` and `xhi`)?
Sample solution of basic problem

GCD example

GCD (Greatest Common Divisor) is a common mathematical problem:

Given two positive natural numbers, what is the largest (positive) natural number which is a divisor for both inputs?

The benefit for us is that GCD is a good example to see the tradeoffs between structural recursion and generative recursion.

A structurally recursive version is rather straightforward -- count down until you find a numbers that divides both inputs. A generative recursive version devised by Euclid requires a "Eureka!".

Here's the code. (Note that these contracts use "N" for natural numbers and "N[≥1]" for natural numbers greater than 1.)

     ; gcd-structural : N[≥1] N[≥1] -> N[≥1]
     ; Return the greatest common divisor of the two inputs.
     ; Algorithm based on structural recursion.
     ; Examples: 
     ;   (gcd-structural 6 25)               = 1
     ;   (gcd-structural 18 24)              = 6
     ;   (gcd-structural 101135853 45014640) = ???
     (define (gcd-structural n m)
       (local [; divides? : N N -> boolean
               ; Return whether i divides n with zero remainder.
               (define (divides? n i)
                 (zero? (remainder n i)))

               ; first-divisor-<= : N[≥1] -> N[≥1]
               ; Return the greatest common divisor of m and n
               ;   that is less than or equal to i.
               (define (first-divisor-<= i)
                 (cond
                   [(= i 1) 1]
                   [else (cond
     	                   [(and (divides? n i) (divides? m i)) i]
    	                   [else (first-divisor-<= (sub1 i))])]))]
         (first-divisor-<= (min m n))))


     ; gcd-generative : N[≥1] N[≥1] -> N[≥1]
     ; Return the greatest common divisor of the two inputs.
     ; Algorithm based on generative recursion.
     ; Examples: 
     ;   (gcd-generative 6 25)               = 1
     ;   (gcd-generative 18 24)              = 6
     ;   (gcd-generative 101135853 45014640) = ???
     (define (gcd-generative n m)
       (local [; euclid-gcd : N N -> N
               ; Return the greatest common divisor of the two inputs.
               ; Assume that larger ≥ smaller.
               (define (euclid-gcd larger smaller)
     	         (cond
                    [(= smaller 0) larger]
                    [else (euclid-gcd smaller (remainder larger smaller))]))]
         (euclid-gcd (max m n) (min m n))))

GCD exercises
Examine both programs, so that you understand them. Test both programs on some example inputs, including some large ones. Explain why the structural algorithm is correct. Explain why the generative algorithm is correct. (Can you?) What is the main advantage of the structural version? What is the main advantage of the generative version?

Ackerman's Function Example

Here's the definition of a strange numerical function on natural numbers, called Ackerman's function:

     A(m,n) = 0,               if n=0
            = 2×n,             if n>0 and m=0
            = 2,               if n=1 and m>0
            = A(m-1,A(m,n-1)), if n>1 and m>0

Note that this definition is not structurally recursive. In fact, it cannot be defined in a structurally recursive manner. (In technical jargon, the function is not primitive recursive. See COMP 481 for what that means.)

Here's the equivalent Scheme code:

(define (ack m n)
   (cond
      [(= n 0)                 0]
      [(and (> n 0) (= m 0))   (* 2 n)]
      [(and (= n 1) (> m 0))   2]
      [(and (> n 1) (> m 0))   (ack (sub1 m) (ack m (sub1 n)))]))

Ackerman's function exercises
Try it out on some inputs. Warning: Try very very small inputs, like 0, 1, 2, 3, and maybe 4, because the result gets very big very fast. Argue why this always terminates (for natural numbers).

This function isn't very useful, except as a function that grows faster than probably any one you've seen before. In COMP 482, you'll learn one use for this function.