Laboratory: Recursion, Revisited

Summary: In this laboratory, you will continue your exploration of recursion.

Contents:

• Preparation
• Exercises
  • Exercise 1: Appending Lists
  • Exercise 2: The Brightest Color
  • Exercise 3: The Brightest Color, Revisited
  • Exercise 4: The Brightest Color, Re-Revisited
  • Exercise 5: Reflect!
  • Exercise 6: Closest Color
  • Exercise 7: Checking for Brightness
• For Those With Extra Time
  • Extra 1: Templates
• Notes
  • Notes on Problem 2: The Brightest Color
  • Notes on Problem 3: The Brightest Color, Revisited
  • Notes on Problem 4: The Brightest Color, Re-Revisited

Preparation

a. Create two lists of colors, one short and one long:

(define a-few-colors (list color.black color.white color.red))
(define lots-of-greens (map cname->rgb (cname.list "green")))

b. Find out how many colors are in lots-of-greens and verify that it is longer than a-few-colors.

c. Add the following procedures to your definitions pane.

;;; Procedure:
;;;   rgb.bright?
;;; Parameters:
;;;   color, an RGB color
;;; Purpose:
;;;   Determine if the color appears bright.
;;; Produces:
;;;   bright?, a Boolean
(define rgb.bright?
  (lambda (color)
     (< 66 (rgb.brightness color))))

;;; Procedure:
;;;   rgb.brightness
;;; Parameters:
;;;   color, an RGB color
;;; Purpose:
;;;   Computes the brightness of color on a 0 (dark) to 100 (bright) scale.
;;; Produces:
;;;   b, an integer
;;; Preconditions:
;;;   color is a valid RGB color.  That is, each component is between
;;;     0 and 255, inclusive.
;;; Postconditions:
;;;   If color1 is likely to be perceived as brighter than color2,
;;;     then (brightness color1) > (brightness color2).
(define rgb.brightness
  (lambda (color)
    (round (* 100 (/ (+ (* .30 (rgb.red color)) 
                        (* .59 (rgb.green color)) 
                        (* .11 (rgb.blue color)))
                      255)))))

;;; Procedure:
;;;   rgb.distance
;;; Parameters:
;;;   color1, an RGB color
;;;   color2, an RGB color
;;; Purpose:
;;;   Finds the distance between color1 and color2 using some metric.
;;; Produces:
;;;   distance, an integer
(define rgb.distance
  (lambda (color1 color2)
    (+ (square (- (rgb.red color1) (rgb.red color2)))
       (square (- (rgb.green color1) (rgb.green color2)))
       (square (- (rgb.blue color1) (rgb.blue color2))))))

Exercises

Exercise 1: Appending Lists

You may recall that the procedure append takes as parameters two lists, and joins the two lists together. Let's generalize that procedure. Write a procedure, lists.join, that, given a list of lists as a parameter, joins each of the member lists together using append.

> (lists.join (list (list 1 2 3)))
(1 2 3)
> (lists.join (list (list 1 2 3) (list 10 11 12)))
(1 2 3 10 11 12)
> (lists.join (list (list 1 2 3) (list 10 11 12) (list 20 21)))
(1 2 3 10 11 12 20 21)
> (lists.join (list null (list 1 2 3) null null null null (list 100 99 98) null))
(1 2 3 100 99 98)

Exercise 2: The Brightest Color

a. Write a procedure, (rgb-list.brightest colors), that, given a list of colors, finds the brightest color in that list. In writing your procedure, use the following structure:

• Base case: If the list has only one element, that element is the brightest.
• First recursive case: If the first element of the list is brighter than the brightest color in the rest of the list, use the first element of the list.
• Second recursive case: If the first element of the list is not brighter than the brightest color in the rest of the list, use the brightest color in the rest of the list. (Note that if the tests for the base case and the first recursive case fail, the test for this case must hold.)

b. When you are done, compare your answer to the solution that appears in the notes on this problem

c. Test this procedure on a-few-colors.

d. Test this procedure on lots-of-greens.

d. What do you expect to have happen if you call this procedure on the empty list of colors?

e. Experimentally check your answer to the previous step.

f. Test this procedure on a few other lists.

Exercise 3: The Brightest Color, Revisited

Is your solution to Exercise 2 the only way to write a recursive procedure to find the brightest color in a list? Certainly not! For example, we might write something that follows the pattern of spot-list.leftmost.

(define spot-list.leftmost
  (lambda (spots)
    (if (null? (cdr spots))
        (car spots)
        (spot.leftmost (car spots) (spot-list.leftmost (cdr spots))))))

What's the key idea in this procedure (other than using recursion and having a singleton base case)? We use a single procedure, spot.leftmost, to handle two cases: The recursive case in which the first element is to the left of the remaining elements, and the case in which the first element is not to the left of the remaining elements.

a. To use this pattern, you'll need to create the equivalent of spot.leftmost, except that it finds the brighter of two colors. Write a procedure, (rgb.brighter color1 color2) that returns the brighter of color1 and color2.

b. Finish your definition of rgb-list.brightest by replacing the appropriate parts of the aforementioned definition.

c. Compare your answer to the one that appears in the notes on this problem.

d. Determine what happens on the empty list.

e. Determine what happens with a-few-colors.

f. Determine what happens with lots-of-greens.

Exercise 4: The Brightest Color, Re-Revisited

In the reading and laboratory on tail recursion, we used a very different technique for writing recursive procedures: In addition to passing along a list that we were recursing over, we also passed along an intermediate result, which we used when we hit the base case. Let's try rewriting rgb.brightest that way.

(define rgb-list.brightest
  (lambda (colors)
     (rgb-list.brightest-helper (car colors) (cdr colors))))
(define rgb-list.brightest-helper
  (lambda (brightest-so-far remaining-colors)
    (if (null? remaining-colors)
        brightest-so-far
        (rgb-list.brightest-helper ____
                                   (cdr remaining-colors)))))

a. Finish this definition.

b. Compare it to the definition in the notes on this problem.

c. Test it on a-few-colors and lots-of-greens.

Exercise 5: Reflect!

You've now come up with (or read) three definitions of rgb-list.brightest. Which do you prefer? Why?

Exercise 6: Closest Color

Write and test a procedure, (rgb-list.closest color colors), that finds the element of colors that is closest to color. You can use your favorite of the three strategies from Exercises 2-4.

Exercise 7: Checking for Brightness

a. Write and test a procedure, (all-bright? colors), that, given a list of colors, determines if all of them are bright. 

b. Write and test a procedure, (any-bright? colors), that, given a list of colors, determines if any of the colors are bright.

For Those With Extra Time

Extra 1: Templates

Write your own fill in the blanks template for the three kinds of recursion covered in Exercises 2-4.

Notes on Problem 2: The Brightest Color

Here's a solution that matches the description given earlier.

(define rgb-list.brightest
  (lambda (colors)
    (cond
      ((null? (cdr colors))
       (car colors))
      ((> (rgb.brightness (car colors)) 
          (rgb.brightness (rgb-list.brightest (cdr colors))))
       (car colors))
      (else (rgb-list.brightest (cdr colors))))))

Notes on Problem 3: The Brightest Color, Revisited

Here's a solution that matches the description given earlier.

(define rgb-list.brightest
  (lambda (colors)
    (if (null? (cdr colors))
        (car colors)
        (rgb.brighter (car colors) (rgb-list.brightest (cdr colors))))))

Notes on Problem 4: The Brightest Color, Re-Revisited

Here's a solution that matches the description given earlier.

(define rgb-list.brightest
  (lambda (colors)
     (rgb-list.brightest-helper (car colors) (cdr colors))))
(define rgb-list.brightest-helper
  (lambda (brightest-so-far remaining-colors)
    (if (null? remaining-colors)
        brightest-so-far
        (rgb-list.brightest-helper 
           (rgb.brighter brightest-so-far (car remaining-colors))
           (cdr remaining-colors)))))

Janet Davis (davisjan@cs.grinnell.edu)