%CustomEntities; %CourseEntities; %CommonEntities; ]>

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.

Here is a template for the simplest kind of numeric recursive procedures. (define recursive-proc (lambda (n) (if (zero? n) base-case (combine n (recursive-proc (- n 1)))))) If you choose to use a helper, here is one common form. (define recursive-proc (letrec ((kernel (lambda (so-far n) (if (zero? n) so-far (kernel (update so-far n) (- n 1)))))) (lambda (n) (kernel starting-value n)))) We can also use a kernel to count up from 1 to n. (A slight change lets you count up from 0 to n.) (define recursive-proc (letrec ((kernel (lambda (so-far i n) (if (> i n) so-far (kernel (update so-far i) (+ i 1) n))))) (lambda (n) (kernel starting-value 1 n))))

a. Make sure that your library includes the following spot procedures. b. Make sure that your library includes the count-from procedure from the reading. c. Open a new window, and make the first line an instruction to load your library. d. Create a new 200x200 and name it canvas. e. Pick your favorite image, load it, and name it picture.

Here is the final definition of termial from the reading. Rewrite it so that the kernel is local.

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 (the first pattern above), 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 Scheme 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 (rgb-new 255 0 0))) (count-down 100)) b. Check your answer by rendering the spots, using an expression like the following. (image-render-stamp! canvas (map (lambda (n) (spot-new n 5 (rgb-new 255 0 0))) (count-down 100))) c. Consider the following expression. Summarize the list of spots it describes. (map (lambda (n) (spot-new 3 n (rgb-new 0 0 255))) (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) (rgb-new 0 0 0))) (count-down 200)) h. Check your answer by rendering the spots.

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 exercise 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 which you added to your library at the beginning of this lab. a. What is the value of the call (count-from -10 10)? b. Check your answer experimentally. c. 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 way of defining count-from?

Write a procedure, (list-nth n lst), that extracts element n of a list. For example, > (list-nth 5 (list "red" "orange" "yellow" "green" "blue" "indigo" "violet">)) "indigo" > (list-nth 0 (list "red" "orange" "yellow" "green" "blue" "indigo" "violet">)) "red" Even though this procedure does the same thing 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: When recursing, you will need to simplify the numeric parameter (probably by subtracting 1) and the list parameter (probably by taking its cdr).

Add the following procedures to your library. 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 mapping an anonymous procedure that includes image-get-spot onto a call to count-down, as in (define image-get-row (lambda (image row) (map (lambda (n) (image-get-spot image ____ ____)) (count-down ____)))) b. Use this procedure to copy a row from picture to canvas. For example, (image-render-stamp! canvas (image-get-row picture 5))

a. Write a procedure, (rectangle width height), that builds a list of positions that correspond to a rectangle of the given width and height with an upper-left-corner of 0,0. 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 3.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 and returns it as a list of spots.

Here's a possible solution to the problem. The base case is easy. If the number is zero, then the list of all non-negative numbers less than or equal to zero is the list that contains only 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 Return to the problem.

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 copies, 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 Return to the problem.