Laboratory: Recursion Basics
In this laboratory, we will not be working with images (just with colors
and with lists), so you need not create an image.
a. Make a copy of recursion-basics-lab.scm, which contains most of the code from the reading.
b. Review the procedures in the file so that you understand their
purpose (if not necessarilly the process by which they acheive their
purpose).
c. Create a list of a dozen or so RGB colors (red, black, green,
blue, yellow, orange, magenta, white, black, etc.). Name it
my-colors. You may find it easiest to create a
list of color names and convert it to RGB colors using
map.
(define my-colors
(map color->rgb
(list "red" "orange" "yellow" "green" "blue" "indigo" "violet"
"black" "white" "grey" "magenta")))
a. Read through sum so that you have a sense of its
approach to accomplishing its purpose
b. Verify that sum produces the same results as in the corresponding reading.
c. What value do you expect sum to produce for the empty
list?
d. Check your answer experimentally.
e. What value do you expect sum to produce for
a singleton list? (A “singleton list” is a list with only
one value.)
f. Check your answer experimentally.
g. Try sum for a few other lists, too.
h. What do you expect the following to compute?
> (sum 1 2 3)
i. Check your answer experimentally.
Exercise 2: Removing Dark Colors
a. Read through the definition of rgb-filter-out-dark to
try to understand what it does.
b. Determine which colors in my-colors are dark with
(map rgb-dark? my-colors).
c. Create a list of non-dark colors with (rgb-filter-out-dark
my-colors).
d. Verify that all the resulting colors are not dark, using a technique
similar to the one that you used in step b.
e. Find out the names of the non-dark colors with
> (map rgb->color-name (rgb-filter-out-dark my-colors))
Exercise 3: Counting Values
Suppose the length procedure, which computes the
length of a list, were not defined. We could define it by recursing
through the list, counting 1 for each value in the list. In some sense,
this is much like the definition of sum, except that we
use the value 1 rather than the value of each element.
a. Using this idea, write a recursive procedure,
(list-length lst)
that finds the length of a list. You may not use
length in defining list-length.
b. Check your answer on a few examples: the empty list, the list of colors
you created, and a few more lists of your choice.
Write a recursive procedure, (product
nums), that computes the product of a
list of numbers. You should feel free to use sum
as a template for product. However, you should
think carefully about the base case.
Exercise 5: Counting Special Values
The length procedure counts the number of values
in a list. What if we don't want to count every value in a list?
For example, what if we only want to count the dark values in a list
of colors? In this case, we still recurse through the list, but
we sometimes count 1 (when the color is dark) and sometimes count 0
(when the color is not dark).
a. Using this idea, write a procedure,
(rgb-tally-dark
colors), that, given a list of colors,
counts how many are dark.
b. Test your procedure.
Exercise 6: Summing Components
In the past, we've found it useful to find the average of two colors. Let's
consider how we might find the average of a list of colors. First, we
would need to find the number of colors in the list. That's easy, we just
use the length procedure. Next, we need to find the sum of
each component. That's a bit harder, but let's suppose we can do it.
We next divide each sum by the length, and get the average of
that component. Finally, we put it all together with rgb-new.
That is, we might write
(define rgb-list-average
(lambda (colors)
(let ((count (length colors)))
(rgb-new (/ (sum-red colors) count)
(/ (sum-green colors) count)
(/ (sum-blue colors) count)))))
Of course, for this to work, we need to write sum-red,
sum-blue, and sum-green. For
now, we'll write one of the three. (One we've written that one,
the other two should be obvious.)
a. Write a procedure, (sum-red
colors), that computes the sum of the
red components in a list of colors. You should use direct recursion
in your definition sum-red. (That is, you
should use recursion, and not take advantage of the already-written
sum procedure, other than as a template for
your code.) You may want to base your definition on the definition
of sum.
b. Test your procedure on a list of a single color.
c. Test your procedure on the my-colors list you wrote earlier.
d. It is possible to write sum-red without
using direct recursion. How? An appropriate combination of
map and sum. Try doing so.
If you can't find a solution, look at the notes on this
problem.
Exercise 7: Filtering Out Reds
Write a procedure, (filter-out-reds
colors), that filters out all elements
of colors with a red component of at least 128.
For Those With Extra Time
Extra 1: The Darkest Color
Write a procedure,
(rgb-darkest colors),
that, given a nonempty list of colors, finds the darkest of those
colors.
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.
Hint: Think about how, given two numbers, you
determine which is closer to zero.
Hint: Think about how this problem is similar to
a problem or problems we've solved before.
Extra 3: Averaging Colors
We've seen how to average two colors and a list of colors. 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.
Once again, the length of the result list is one less than the length
of the input list.
