Summary: Although most of our prior experiments with recursion have emphasized recursion over lists, it is also possible to use other values as the basis of recursion. In this laboratory, you will explore the use of natural numbers (non-negative integers) as the basis of recursion.
Contents:
a. If you have not already done so, create a library file that you will use
to save important procedures. For example, you might name the file
/home/username/library.sct.
b. The file spots.sct
summarizes most of the procedures for manipulating spots that we've
written in previous libraries. Right-click on the preceding link, and
save this file as /home/username/spots.sct.
c. Open a new window, and enter instructions to load
your library and spots.sct.
d. Create a new 200x200 and name it canvas.
e. Pick your favorite image, load it, and name it picture.
Define and test a recursive Scheme procedure, (count-down
val), that takes a natural number as argument and returns
a list of all the natural numbers less than or equal to that number,
in descending order:
> (count-down 5)
(5 4 3 2 1 0)
> (count-down 0)
(0)
Note that you should use cons to build up the list.
Note also that you are better off writing this with direct recursion, rather than using a helper procedure.
When you are finished, you may want to read the notes on this exercise.
When you are finished writing this procedure, add count-down to your library.
As you may recall from some of the earlier labs, sometimes we want to
draw sequences of spots. In those past exercises, we generated the list
of spot positions by hand. One of the great benefits of procedures like
count-down is that they can help us automate the generation
of a large number of spots.
a. Consider the following expression. Summarize the list of spots it describes.
(map (lambda (n) (spot.new n 5 color.red)) (count-down 100))
b. Check your answer by rendering the spots, using an expression like the following.
(image.render-spots! canvas
(map (lambda (n) (spot.new n 5 color.red)) (count-down 100)))
c. Consider the following expression. Summarize the list of spots it describes.
(map (lambda (n) (spot.new 3 n color.blue)) (count-down 50))
d. Check your answer by rendering the spots.
e. Consider the following expression. Summarize the list of spots it describes.
(map (lambda (n) (spot.new n n (rgb.new 0 (* 2 n) 0))) (count-down 128))
f. Check your answer by rendering the spots.
g. Consider the following expression. Summarize the list of spots it describes.
(map (lambda (n) (spot.new (quotient n 10) (modulo n 10) color.black))
(count-down 200))
h. Check your answer by rendering the spots.
a. Write a procedure, (image.get-row image
row), that extracts a row of spots from image. You
should be able to write this procedure by applying image.get-spots
to the result of mapping some function onto a call to count-down,
as in
(define image.get-row
(lambda (image row)
(image.get-spots image (map ____ (count-down ____)))))
b. Use your procedure to copy rows of pixels from picture to canvas. For example,
(image.render-spots! canvas (image.get-row picture 5))
c. Experiment with using spot-list.htrans and spot-list.vtrans to draw the row of spots in different locations on canvas.
d. Now, fill in the following expression to draw the same row of spots five times in canvas:
(define spots (image.get-row picture 20))
(foreach! (lambda (___) (image.render-spots! canvas (spot-list.vtrans spots ___))
(count-down 5)))
Kind of cool, eh?
Define and test a Scheme procedure, (value.replicate value
count), that takes two arguments, the second of which is a
natural number, and returns a list consisting of the specified number of
repetitions of the first argument:
> (value.replicate "sample" 5)
("sample" "sample" "sample" "sample" "sample")
> (value.replicate 10 3)
(10 10 10)
> (value.replicate null 1)
(())
> (value.replicate null 2)
(() ())
> (value.replicate "hello" 0)
()
Even if you know a built-in procedure to do this task, please
implement value.replicate recursively.
When you are finished writing this procedure, compare it to the notes on this problem and then
add value.replicate to your Scheme library.
Define and test a recursive Scheme procedure that takes a natural number
as argument and returns a list of all the natural numbers that are
strictly less than the argument, in ascending order. (The traditional
name for this procedure is iota, a Greek letter.)
For example,
> (iota 3)
(0 1 2)
> (iota 5)
(0 1 2 3 4)
> (iota 1)
(0)
Note that you will probably need to use a helper of some sort to write
iota. You might use the traditional form of helper, which
adds an extra parameter. You might also use a helper that simply
computes iota in the reverse order. (Most students write
a backwards iota in the first attempt; instead of throwing it away,
rename it and call it from iota.)
When you are done, add iota to your library.
You may recall the count-from procedure from
the reading on recursion
over natural numbers. That procedure is also reproduced
at the end of this lab.
What is the value of the call (count-from -10 10)?
a. Write down what you think that it should be.
b. Copy the definition of
count-from
into DrScheme and use it to find out what the call
actually returns.
c. Note that it is possible to implement count-from in terms
of iota. The implementation looks something like the following.
(define count-from
(lambda (lower upper)
(map (lambda (n) (+ _____ n)) (iota _____))))
Finish this definition.
d. What do you see as the advantages and disadvantages of each definition?
e. When you are finished writing this procedure, add the original count-from to your Scheme library.
Write a procedure, (my-list-ref n lst), that
extracts the nth element of a list. For example,
> (my-list-ref 5 (list "red" "orange" "yellow" "green" "blue" "indigo" "violet">))
"indigo"
> (my-list-ref 0 (list "red" "orange" "yellow" "green" "blue" "indigo" "violet">))
"red"
Even though this procedure does the samething as list-ref, you
should not use list-ref to implement it. Instead, your goal
is to figure out how list-ref works, which means that you will
need to implement this procedure using direct recursion.
Hint: You will need to simplify the numeric parameter (probably by subtracting 1) and the list parameter (probably by taking its cdr).
a. Write a procedure, (rectangle width height),
that builds a list of positions that correspond to a rectangle of the given
width and height. For example, if width is 3 and height is 2, the points
will be some permutation of (0,0), (0,1), (0,2), (1,0), (1,1), and (1,2).
Hint: Look at problem 2.g.
b. Write a procedure, (rectangular-region left top width height), that builds a list of positions that
correspond to a rectangular region as described.
c. Write a procedure, (image.get-region image left top width height), that extracts a rectangular image from
the given image.
Here's a possible solution to the problem. The base case is easy. If the number is zero, the list of all non-negative numbers less than or equal to zero is the list of zero.
(if (zero? n)
(list 0)
In the recursive case, we assume that we can compute the list of all numbers less than or equal to n-1. To get the complete list, we simply add n to the front.
(cons n (count-down (- n 1)))
Putting it all together, we get
(define count-down
(lambda (n)
(if (zero? n)
(list 0)
(cons n (count-down (- n 1))))))
We begin by considering the base case. The last example gives a hint: If you want zero copies, you end up with the empty list.
(if (zero? n)
null
Now, on to the recursive case. If we can create a list of n-1 opies, we can then create a list of n copies by prepending one more copy.
(cons val (value.replicate val (- n 1)))
Putting it all together, we get
(define value.replicate
(lambda (val n)
(if (zero? n)
null
(cons val (value.replicate val (- n 1))))))
count-from
Here is the count-from procedure from
the reading.
;;; Procedure:
;;; count-from
;;; Parameters:
;;; lower, a natural number
;;; upper, a natural number
;;; Purpose:
;;; Construct a list of the natural numbers from lower to upper,
;;; inclusive, in ascending order.
;;; Produces:
;;; ls, a list
;;; Preconditions:
;;; lower <= upper
;;; Both lower and upper are numbers, exact, integers, and non-negative.
;;; Postconditions:
;;; The length of ls is upper - lower + 1.
;;; Every natural number between lower and upper, inclusive, appears
;;; in the list.
;;; Every value in the list with a successor is smaller than its
;;; successor.
;;; For every natural number k less than or equal to the length of
;;; ls, the element in position k of ls is lower + k.
(define count-from
(lambda (lower upper)
(if (= lower upper)
(list upper)
(cons lower (count-from (+ lower 1) upper)))))
Janet Davis (davisjan@cs.grinnell.edu)
Created October 11, 2007 based on http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2007F/Labs/numeric-recursion-lab.html