# Numeric Recursion

This lab is also available in PDF.

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:

## Preparation

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. Add the spot procedures that we've written in previous laboratories to your library. (If you don't remember those procedures, you can find them in an appendix.) Save the file.

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

## Exercises

### Exercise 1: Counting Down

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

### Exercise 2: Drawing Sequences of Spots

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

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

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

### Exercise 3: Filling Lists

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.

### Exercise 4: Counting To

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.

### Exercise 5: Counting Between

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.

### Exercise 6: Extracting Rows

a. Write a proceudre, ```(image.get-row image row)```, that extracts a row of spots from image. You should be able to write this procedure by appling `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 this procedure to copy a row from `picture` to `canvas`. For example,

```(image.render-spots! canvas (image.get-row picture 5))
```

c. Experiment with using `spots.htrans` and `spots.vtrans` to draw the row of spots in different locations on canvas.

d. Pick a row of spots from `picture` and name it `myrow`.

e. Using `foreach!` and `count-down`, write a procedure that draws the `myrow` in five successive rows of `canvas`

## For Those Who Finish Early

### Extra 1: The Nth Element

Write a procedure, `(list.nth n lst)`, that extracts the nth element 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 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).

### Extra 2: Extracting Rectanular Regions

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.

## Notes

### Notes on Exercise 1: Counting Down

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

### Notes on Exercise 3: Filling Lists

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

## Useful Procedures

### Procedures for Manipulating Spots

```;;; Procedure:
;;;   spot.new
;;; Parameters:
;;;   col, an integer
;;;   row, an integer
;;;   color, an RGB color
;;; Purpose:
;;;   Create a simple representation of spots.
;;; Produces:
;;;   newspot, a spot
;;; Preconditions:
;;; Postconditions:
;;;   newspot is a spot.
;;;   (spot.col spot) is col.
;;;   (spot.row spot) is row.
;;;   (spot.color spot) is color.
(define spot.new
(lambda (col row color)
(list col row color)))

;;; Procedure:
;;;   spot.col
;;; Parameters:
;;;   spot, a spot
;;; Purpose:
;;;   Extract the column from the spot.
;;; Produces:
;;;   column, an integer
;;; Preconditions:
;;;   spot is a spot, as created by spot.new (or an equivalent procedure).
;;; Postconditions:
;;;   column is the column associated with the spot, the value
;;;     provided as the first parameter to spot.new.
(define spot.col car)

;;; Procedure:
;;;   spot.row
;;; Parameters:
;;;   spot, a spot
;;; Purpose:
;;;   Extract the row from the spot.
;;; Produces:
;;;   row, an integer
;;; Preconditions:
;;;   spot is a spot, as created by spot.new (or an equivalent procedure).
;;; Postconditions:
;;;   row is the row associated with the spot, the value
;;;     provided as the second parameter to spot.new.

;;; Procedure:
;;;   spot.color
;;; Parameters:
;;;   spot, a spot
;;; Purpose:
;;;   Extract the color from the spot.
;;; Produces:
;;;   color, an integer
;;; Preconditions:
;;;   spot is a spot, as created by spot.new (or an equivalent procedure).
;;; Postconditions:
;;;   color is the color associated with the spot, the value
;;;     provided as the third parameter to spot.new.

;;; Procedure:
;;;   spot?
;;; Parameters:
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine whether val is a spot.
;;; Produces:
;;;   is-spot, a Boolean
;;; Preconditions:
;;; Postconditions:
;;;   If val can reasonably be interpreted as a spot (a value created
;;;     by spot.new or the equivalent), then is-spot is true (#t).
;;;   Otherwise, is-spot is false (#f).

;;; Procedure:
;;;   spots.htrans
;;; Parameters:
;;;   spots, a list of spots
;;;   amt, an integer
;;; Purpose:
;;;   Translate each spot in spots horizontally by amount.
;;; Produces:
;;;   translated, a list of spots
;;; Preconditions:
;;; Postconditions:
;;;   For each i, 0 <= i < (length spots)
;;;    (spot.col (list-ref translated i)) = (+ amt (spot.col (list-ref spots i)))
(define spots.htrans
(lambda (spots amt)
(map
(lambda (s) (spot.new (+ amt (spot.col s)) (spot.row s) (spot.color s)))
spots)))

;;; Procedure:
;;;   spots.vtrans
;;; Parameters:
;;;   spots, a list of spots
;;;   amt, an integer
;;; Purpose:
;;;   Translate each spot in spots verticaly by amount.
;;; Produces:
;;;   translated, a list of spots
;;; Preconditions:
;;; Postconditions:
;;;   For each i, 0 <= i < (length spots)
;;;    (spot.row (list-ref translated i)) = (+ amt (spot.row (list-ref spots i)))
(define spots.vtrans
(lambda (spots amt)
(map
(lambda (s) (spot.new (spot.col s) (+ amt (spot.row s)) (spot.color s)))
spots)))

;;; Procedure:
;;;   image.render-spot!
;;; Parameters:
;;;   image, an image
;;;   spot, a spot
;;; Purpose:
;;;   Render spot on image.
;;; Produces:
;;;   [Nothing of import; called for the side effect]
;;; Preconditions:
;;;   spot is a valid spot.
;;;   image is a valid image.
;;;   The spot can appear on the image.  That is
;;;     0 <= (spot.col spot) < (image.width image)
;;;     0 <= (spot.row spot) < (image.height image)
;;; Postconditions:
;;;   The pixel in the image that corresponds to spot now contains the
;;;     color of the spot.  That is,
;;;     (image.get-pixel image (spot.col spot) (spot.row spot))
;;;       is (spot.color spot)
(define image.render-spot!
(lambda (image spot)
(if (and (>= (spot.col spot) 0) (< (spot.col spot) (image.width image))
(>= (spot.row spot) 0) (< (spot.row spot) (image.height image)))
(image.set-pixel! image (spot.col spot) (spot.row spot) (spot.color spot)))))

;;; Procedure:
;;;   image.render-scaled-spot!
;;; Parameters:
;;;   image, an image
;;;   spot, a spot
;;;   scale, a positive integer
;;; Purpose:
;;;   Render an enlarged version of spot on image.
;;; Produces:
;;;   [Nothing of import; called for the side effect]
;;; Preconditions:
;;;   spot is a valid spot.
;;;   image is a valid image.
;;;   The spot can appear on the image.   That is,
;;;     0 <= (* scale (spot.col spot)) < (image.width image)
;;;     0 <= (* scale (spot.row spot)) < (image.height image)
;;; Postconditions:
;;;   For any point in image that is in the scale-by-scale grid whose
;;;   upper-left corner is at
;;;     ((* scale (spot.col spot)), (* scale (spot.row spot))),
;;;     (image.get-pixel image x y) = (spot.color spot)
(define image.render-scaled-spot!
(lambda (image spot scale)
(region.compute-pixels!
image
(* scale (spot.col spot)) (* scale (spot.row spot))
(+ scale -1 (* scale (spot.col spot))) (+ scale -1 (* scale (spot.row spot)))
(lambda (pos) (spot.color spot)))))

;;; Procedure:
;;;   image.render-spots!
;;; Parameters:
;;;   image, an image
;;;   spots, a list of spots
;;; Purpose:
;;;   Render a list of spots on the image.
;;; Produces:
;;;   [Nothing; called for the side effect]
;;; Preconditions:
;;;   Each element of spots meets the preconditions for image.render-spot!.
;;; Postconditions:
;;;   Each element of spots is rendered on image at the position that
;;;     corresponds to the spot.
(define image.render-spots!
(lambda (image spots)
(foreach! (lambda (spot) (image.render-spot! image spot)) spots)))

;;; Procedure:
;;;   image.render-scaled-spots!
;;; Parameters:
;;;   image, an image
;;;   spots, a list of spots
;;    scale, a non-negative integer
;;; Purpose:
;;;   Render a list of spots on the image, with each spot scaled by scale.
;;; Produces:
;;;   [Nothing; called for the side effect]
;;; Preconditions:
;;;   Each element of spots meets the preconditions for
;;;     image.render-scaled-spot!.
;;; Postconditions:
;;;   Each element of spots is rendered on image in a scale-by-scale grid
;;;     (or the closest approximation that fits), starting at
;;;     ((* scale (spot.col spot)), (* scale (spot.row spot))),
(define image.render-scaled-spots!
(lambda (image spots scale)
(foreach! (lambda (spot) (spot.render-scaled-spot! image spot scale)) spots)))

;;; Procedure:
;;;   image.get-spots
;;; Parameters:
;;;   image, an image
;;;   positions, a list of positions
;;; Purpose:
;;;   Gets a spot from image for each position in positions.
;;; Produces:
;;;   spots, a list of spots
;;; Preconditions:
;;;   Each position in positions is within the image
;;; Postconditions:
;;;   (length spots) = (length positions)
;;;   For each i, 0 <= i < (length spots)
;;;     (list-ref spots i) = (image.get-spot image (list-ref positions i))
(define image.get-spots
(lambda (image positions)
(map (lambda (pos) (image.get-spot image pos)) positions)))

;;; Procedure:
;;;   image.get-spot
;;; Parameters:
;;;   image, an image
;;;   pos, a position
;;; Purpose:
;;;   Get a spot from the image
;;; Produces:
;;;   spot, a spot
;;; Preconditions:
;;;   pos is a valid position in image
;;; Postconditions:
;;;   (spot.col spot) = (position.col pos)
;;;   (spot.row spot) = (position.row pos)
;;;   (spot.color spot) =
;;;     (image.get-pixel image (position.col pos) (position.row pos))
(define image.get-spot
(lambda (image pos)
(spot.new (position.col pos)
(position.row pos)
(image.get-pixel image (position.col pos) (position.row pos)))))
```

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

## History

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Mon Dec 3 09:55:14 2007.
The source to the document was last modified on Thu Oct 18 12:27:05 2007.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2007F/Labs/numeric-recursion-lab.html`.

You may wish to validate this document's HTML ; ;

Samuel A. Rebelsky, rebelsky@grinnell.edu

Copyright © 2007 Janet Davis, Matthew Kluber, and Samuel A. Rebelsky. (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. To view a copy of this license, visit `http://creativecommons.org/licenses/by-nc/2.5/` or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.