Generative Recursion

Instructions for students & labbies: Students use DrScheme, following the design recipe, on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention.

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., 0.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. What are some other approaches for determining when to stop the recursion (i.e., what is "close enough")? Generalize your algorithm by introducing a function argument that tells us when we're "close enough" to use the base case. Similarly, generalize your algorithm by introducing a function argument for computing the base case approximation, using a rectangular, trapezoidal, or whatever other approximation we might want. Instead of recurring on halves of the x-interval, what other approaches might you take? How could we generalize the algorithm to 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

Insertion Sort vs. Mergesort

In class, we've described two different ways of sorting numbers, insertion sort and quicksort.

      (define (isort l)
         (cond
            [(empty? l) empty]
            [(cons? l)  (insert (first l) (isort (rest l)))]))

      (define (insert new sortedl)
         (cond
            [(empty? sortedl) (list new)]
            [else
             (cond
                 [(< new (first sortedl))
                  (cons new sortedl)]
                 [else
                  (cons (first sortedl)
                        (insert new (rest sortedl)))])]))

      ;;;;;;;;;;;;;;;;;

      (define (qsort l)
         (cond
            [(empty? l) empty]
            [(cons? l)
             (local [(define pivot (first l))
                     (define lt (filter (lambda (n) (< n pivot)) l))
                     (define eq (filter (lambda (n) (= n pivot)) l))
                     (define gt (filter (lambda (n) (> n pivot)) l))]
                (append (qsort lt)
                        eq
                        (qsort gt)))]))

So we have two fundamentally different approaches to sorting a list (and there are lots of others, too). It seems unsurprising that each might behave differently. Can we observe this difference? Can we provide explanations? We'll do some timing experiments, outline the theoretical analysis, and see if the two jive.

If your programs only sort small lists a few times, it doesn't matter; any sort that is easy to write and have correct is fine. However, for longer lists, the difference really is huge. In Real Life (tm), sorting is an operation often done on very long lists (repeatedly).

There is an expression (time expr), which can be used to time how long it takes the computer to evaluate something. It is used like

      (time (isort big-list))

where big-list would be previously defined. This expression prints out the time taken during evaluation, along with the evaluation result. Since we're only interested in the time, we can avoid seeing the long sorted list by using something like

      (time (empty? (isort big-list)))

time prints three times, each in milliseconds. The first is the amount of computing time elapsed -- thus, it doesn't count whatever else your computer was doing at the same time. This is what we're interested in.

Timing Exercises

Partner with someone else in lab to split the following work. First, we need some data to use for our timing experiments. Write a function nums-up which creates a list of naturals in ascending order. E.g., (nums-up 7) returns (list 0 1 2 3 4 5 6). Hint: Use build-list or dig out your solution from a previous lab. Similarly, write nums-down, where (nums-down 7) returns (list 6 5 4 3 2 1 0). Now write a function nums-rand, which similarly creates a list of random numbers in the range from 0 to 32767. To create a single random numbers in the range from 0 to 9, you could use (random 10). For larger numbers, try: (define max-rand 32768) (random max-rand) ; random is built-in (Note that random is certainly a function in the Scheme sense, but not in the mathematical sense, since the output is not determined by the input.) Now, make sure you know how to use time. Time isort on a list of 200 elements. Run the exact same expression again a couple times. Note that the time varies some. We typically deal with such variation by taking the average of several runs. The variation is caused by a number of low-level hardware reasons that are beyond the scope of this course (see ELEC 220 and COMP 320). Continue timing, filling in the following chart. When you're done, compare results with other pairs in the lab. input size 200 1000 5000 isort up   up   up   down   down   down   rand   rand   rand   qsort up   up   up   down   down   down   rand   rand   rand

COMP 280 introduces concepts of how these algorithms behave in general. The punchline is that we can say that both insertion sort and quicksort on lists are "O(n²)" in the worst case. I.e., for a list of n elements, they each take about c × n² evaluation steps to sort the list, for some constant c. Furthermore, in the "average" case, Quicksort does better:

O(n log n). COMP 280, and later COMP 482, show precisely what these statements mean and how to derive them.

Ackermann's Function Example

If you have time…

Here's the definition of a strange numerical function on natural numbers, called Ackermann'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)))]))

Ackermann'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 theoretical example of a function that grows faster than probably any one you've seen before. In COMP 482, you'll learn one use for this function.