Assignment 7: List Recursion


Due: 10:30 p.m., Tuesday, 30 October 2012

Summary: You will apply the basic and helper recursion patterns to a short series of problems.

Purposes: To practice writing a variety of procedures that perform recursion over lists.

Expected Time: Two to three hours.

Collaboration: We encourage you to work in groups of size three. You may, however, work alone or work in a group of size two.

Submitting: Email your answer to . The title of your email should have the form CSC151-02 Assignment 7: List Recursion and should contain your answers to all parts of the assignment. Scheme code should be in the body of the message.

Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.

Preliminaries

You may wish to review the summary of recursion patterns.

Your procedures need not verify their preconditions, except as directed in your solution to Problem 4, part c.

Assignment

Problem 1: Closest to Zero

a. Write a procedure, (closest-to-zero values), that, given a list of real numbers (including both positive and negative numbers), returns the value closest to zero in the list. Your solution should use basic recursion.

Hint: Think about how, given two numbers, you determine which is closer to zero.

b. Write a second version of closest-to-zero that uses helper recursion. That is, you should have an additional helper procedure that takes closest-so-far and remaining as parameters.

c. Explain which version of closest-to-zero you prefer and why.

Problem 2: A Safer Sum

Write and document a procedure (safe-sum values) that, given a list of values as a parameter, computes the sum of the numeric values in the list. That is, safe-sum should ignore all non-numeric values.

> (safe-sum (list 1 2 3))
6
> (safe-sum (list 3 'a 'b 5))
8
> (safe-sum (list 'a 'b))
0

Problem 3: Averaging Colors

Averaging two colors is a fairly simple task: simply average each of the respective red, green, and blue components, as in the following procedure.

;;; Procedure:
;;;   rgb-average
;;; Parameters:
;;;   rgb1, an RGB color
;;;   rgb2, an RGB color
;;; Purpose:
;;;   Compute the "average" of two RGB colors.  
;;; Produces:
;;;   rgb-avg, an RGB color
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (rgb-red rgb-avg) is the average of (rgb-red rgb1) and (rgb-red rgb2)
;;;   (rgb-green rgb-avg) is the average of (rgb-green rgb1) and (rgb-green rgb2)
;;;   (rgb-blue rgb-avg) is the average of (rgb-blue rgb1) and (rgb-blue rgb2)
(define rgb-average
  (lambda (rgb1 rgb2)
    (rgb-new (quotient (+ (rgb-red rgb1) (rgb-red rgb2)) 2)
             (quotient (+ (rgb-green rgb1) (rgb-green rgb2)) 2)
             (quotient (+ (rgb-blue rgb1) (rgb-blue rgb2)) 2))))

We also saw how to average a list of colors in the lab on Recursion Basics. But what if we want to do something different: Given a list of colors, we want averages, but only of neighboring elements in the list.

Write a procedure, (rgb-averages colors), that, given a list of colors, computes a new list of colors, by averaging subsequent pairs of colors. For example, if the input list is the standard seven rainbow colors (red, orange, yellow, green, blue, indigo, and violet), the output list will consist of a red-orange average, an orange-yellow average, a yellow-green average, a green-blue average, a blue-indigo average, and an indigo-violet average.

The length of the resulting list will be one less than the length of the input list.

Problem 4: Reversing lists

a. Using the 6 P's, document the reverse procedure.

b. Suppose the reverse procedure were not included in Scheme. Could you write it yourself? Certainly! It should be possible to implement reverse recursively.

Using the helper recursion pattern, implement your own version of reverse called my-reverse.

c. Modify my-reverse so that it verifies its preconditions.

Important Evaluation Criteria

Students who provide correct procedures for each question will earn a check.

Students who provide oddly formatted or inelegant solutions to the problems may be publicly critiqued for their odd formatting and inelegance, and will also receive a check-.

Students who provide particularly elegant formatting or strategies will earn a check+.


Jerod Weinman

Copyright 2007-2012 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)

This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License .