Exam 3: Recursion

Topics: Recursion over lists, named let, code reading, documentation

Consider the following interesting procedure definition.

(define s
  (lambda (l)
    (let kernel ([a null]
                 [b null]
                 [c l])
      (cond
        [(null? c)
         (list (reverse a) (reverse b))]
        [(number? (car c))
         (kernel (cons (car c) a) b (cdr c))]
        [else
         (kernel a (cons (car c) b) (cdr c))]))))

Figure out what this program does and then do the following.

a. Rename the procedure and the parameters so that they will make sense to the reader.

b. Explain why there are two calls to reverse in the base case.

c. Write 6P-style documentation for the code.

Topics: Integer-encoded RGB colors, list recursion

We've seen in the past that a simple metric for the “distance” between two colors is the sum of the squares of the differences between their individual components.

;;; Procedure:
;;;   irgb-distance
;;; Parameters:
;;;   color1, an integer-encoded RGB color
;;;   color2, an integer-encoded RGB color
;;; Purpose:
;;;   Find the distance between color1 and color2, using some simple
;;;   metric for distance.
;;; Produces:
;;;   distance, a non-negative real number
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   If color1=color2, then distance is 0
;;;   For any three colors, a, b, and c, if 
;;;     (irgb-distance a b) < (irgb-distance b c)
;;;   then a is likely to be perceived as being closer to b than c.
;;; Plus:
;;;   irgb-distance is commutative.  That is, for any two colors, a and b,
;;;     (irgb-distance a b) = (irgb-distance b a)
(define irgb-distance
  (lambda (color1 color2)
    (+ (square (- (irgb-red color1) (irgb-red color2)))
       (square (- (irgb-green color1) (irgb-green color2)))
       (square (- (irgb-blue color1) (irgb-blue color2))))))

Once we have such a metric, it's reasonable to ask which color in a list is “closest” to a target color. (That is, which color has the least distance to color.) In a recent examination, you saw a procedure that found which of four colors was closest to an initial color. Now that we know recursion, it seems like we should be able to do better. In particular, we might find the element of a list which is closest to an original color. Here's documentation for such a procedure.

;;; Procedure:
;;;   irgb-closest
;;; Parameters:
;;;   original, an integer-encoded RGB color
;;;   colors, a non-empty list of integer-encoded RGB colors
;;; Purpose:
;;;   Find the element of colors that is "closest" to original.
;;; Produces:
;;;   closest, an integer-encoded RGB color
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   closest is a member of colors.
;;;   For all colors, c, in colors
;;;     (irgb-distance original closest) <= (irgb-distance original c)

Implement irgb-closest.

Topics: Direct recursion over lists, core list operations

As you know, the car grabs the element at the front of the list the cdr grabs all but the element at the front of the list. Of course, there are times that it's useful to work from the back of the list, rather than the front. Hence, we might want a procedure to grab the last element (we'll call that rac) and a procedure to grab all but the last element (we'll call that rdc).

It is possible to implement both rac and rdc with a call to reverse. But that may be inefficient, since reverse builds a new list. It is also possible to implement rac using list-ref with an index of one less than the length of the list. But that's also inefficient, since we have to traverse the list twice, once to find its length, and once to extract the element.

So, what should we do? Not so surprisingly, we can implement both rac and rdc recursively.

Document and write recursive versions of rac and rdc. You should use direct recursion and should not use any helper procedures. (Note: “direct recursion” is what we have also called “basic recursion”.)

In developing your solution, you may certainly rely on car, cdr, cons, and null?. However, you may not rely on other list procedures, such as list-ref, list-take, or list-drop. (If you are unsure as to whether or not you can use a procedure, ask.)

Topics: Numeric recursion, strings, testing

It is often useful to determine whether one string appears within another string. For example, we might want to know whether a faculty member is a rebel by checking for the appearance of the word “rebel” in their name. Consider the following implementation of index-of-substring, which is supposed to achieve that purpose.

;;; Procedure:
;;;   index-of-substring
;;; Parameters:
;;;   str, a string
;;;   substr, a string
;;; Purpose:
;;;   Find the index of an instance of substr in str.
;;; Produces:
;;;   pos, an integer or #f
;;; Preconditions:
;;;   No additional.
;;; Postconditions:
;;;   If substr is not contained in str, then pos is #f
;;;   If substr is contained within str, then pos is a non-negative
;;;   integer and 
;;;     0 <= pos < (string-length str)
;;;     substr appears as a substring of str, with the initial character
;;;     of substr at position pos of str.  That is,
;;;     (equal? (substring str pos (+ pos (string-length substr))) substr)
;;;   If substr appears multiple times within str, then pos may indicate
;;;     any of the appearances.
(define index-of-substring
  (lambda (str substr)
    (let ([substr-len (string-length substr)])
      (let kernel ([pos 0]
                   [finish (- (string-length str) substr-len)])
        (cond 
          [(= pos finish)
           #f]
          [(equal? substr (substring str pos (+ pos substr-len)))
           pos]
          [else
           (kernel (+ 1 pos) finish)])))))

Here is a simple test suite that someone developed for this procedure.

(define contains-tests
  (test-suite
   "Tests of string-contains"
   (check-equal? (index-of-substring "banana" "ban") 
                  0 
                  "start of string")
   (check-equal? (index-of-substring "banana" "nan") 
                  2
                  "middle of string")
   (check-false (index-of-substring "banana" "NAN") 
                 "incorrect capitalization")
   (check-false (index-of-substring "banana" "orange")
                 "mismatched fruit")))

Although the procedure passes the given tests, it is not correctly implemented. In fact, there are at least two different situations in which this procedure gives an incorrect result.

a. Add two distinct checks for which the given implementation of index-of-substring fails.

What do we mean by distinct? The relationship between substr and str should be different in each case. As a counterexample, the following two tests are not distinct because they test essentially the same thing, a matching substring at the start of the string.

   (check-equal? (index-of-substring "banana" "ban") 
                  0)
   (check-equal? (index-of-substring "pineapple" "pine") 
                  0)

b. Once you have found additional errors in this implementation, develop a correct implementation. (You may find it useful to add even more tests.)

Topics: Repetition (through numeric recursion), pixel-based images, randomness.

Consider the following algorithm for drawing a shape.

Repeat many times:

We call this a Monte Carlo method; just like there is randomness at a casino, there is randomness in our method. You could think of this approach to drawing as like spray-painting through a stencil: each position inside the shape has some probability of being painted, but it's unpredictable which ones will actually be chosen.

Write, but do not document, a procedure, (stencil-quarter-circle radius n color). Your procedure should use the following algorithm.

The result should look something like this:

> (image-show (stencil-quarter-circle 100 5000 (irgb 0 0 0)))

Topics: Numeric recursion, randomness

The technique you just used to “spray-paint” a quarter-circle forms the basis of a Monte Carlo method for estimating the value of pi.

Consider the quarter-circle with radius 1. We select N random points where both the x and y values fall between 0 and 1. As we go along, we count how many of those points fall within the quarter-circle; call this M.

Observe that M/N is equal to the ratio between the area of the quarter-circle and the area of the unit square. So, we estimate that pi is approximately M/N * 4, and produce this value.

The larger N is, the better our estimate will be.

Write and document a procedure, (estimate-pi n), which implements this algorithm.

In your sample output, show that providing larger values of n leads to increasingly precise estimates. For example:

> pi
3.141592653589793
> (estimate-pi 10)
3.6
> (estimate-pi 100)
3.0
> (estimate-pi 1000)
3.204
> (estimate-pi 10000)
3.1304
> (estimate-pi 100000)
3.1503
> (estimate-pi 1000000)
3.141568