*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 `<grader-151-02@cs.grinnell.edu>`

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

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.

a. Write a procedure, `(`

, 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.
`closest-to-zero`

* values*)

*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`

c. Explain which version of `closest-to-zero`

you
prefer and why.

Write and document a procedure
`(`

that, given a list of values as a parameter, computes the sum of the
numeric values in the list. That is, `safe-sum`

* values*)

`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`

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, `(`

, 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.
`rgb-averages`

`colors`

)

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

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.

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+.

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.

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