Comp 210 Lab 9: Generative Recursion

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

Design recipe Derivative 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:


Integral 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. 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, the shape under the curve looks a lot like a rectangle or a trapezoid. Either of these turn out to be good approximations, if we have some definition of "close enough". A simple definition of "close enough" is some fixed x-distance threshold, e.g., .001.

integrate exercise
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.

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:

     ; 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
  1. Examine both programs, so that you understand them.
  2. Test both programs on some example inputs, including some large ones.
  3. Explain why the structural algorithm is correct.
  4. Explain why the generative algorithm is correct. (Can you?)
  5. What is the main advantage of the structural version?
  6. 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
            = 2n,              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.)

Ackerman's function exercises
  1. Write a Scheme program for this function.
  2. 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.
  3. 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.