# Deep Recursion

Summary: In this laboratory, you will further explore issues of deep recursion introduced in the reading on pairs and pair structures.

Contents:

## Exercises

### Exercise 0: Preparation

a. Review the material from the reading on pairs and pair structures.

b. Start DrScheme.

### Exercise 1: Number Trees

Recall that a list is a data structure defined recursively as follows:

• The empty list is a list.
• Cons of a value and a list is a list.

Write a similar recursive definition for number trees, trees built from only numbers and cons cells.

### Exercise 2: A Number Tree Predicate

Using your recursive definition of number trees from the previous probelm, write a procedure, `(number-tree? val)` that returns true if val is a number tree and false otherwise.

### Exercise 3: Summing Number Trees

Consider again the `sum-of-number-tree` procedure from the reading, which you can find repeated at the end of this lab.

a. Verify that it works as advertised on the first example.

```(sum-of-number-tree (cons (cons (cons 0 1)
(cons 2 3))
(cons (cons 4 5)
(cons 6 7))))
```

b. What do you expect `sum-of-number-tree` to return when given `(cons 10 11)` as a parameter? Verify your answer experimentally.

c. Verify that it works as advertised on a single number.

d. Verify that it works as advertised on a pair of numbers.

e. What do you expect `sum-of-number-tree` to return when given the empty list as a parameter? Verify your answer experimentally.

f. What do you expect `sum-of-number-tree` to return when given `(list 1 2 3 4 5)` as a parameter? Verify your answer experimentally.

### Exercise 4: Preconditions

a. What preconditions should `sum-of-number-tree` have?

b. Rewrite `sum-of-number-tree` so that it reports an appropriate error if its preconditions are not met.

c. Some programmers consider it inappropriate to scan a tree twice, once to make sure that it's valid and once to compute a value based on the tree. Rewrite `sum-of-number-tree` so that it checks for and reports errors only when it is at one of the non-pair nodes.

### Exercise 5: Counting Cons Cells

a. Define and test a procedure named `cons-cell-count` that takes any Scheme value and determines how many boxes would appear in its box-and-pointer diagram. (The data structure that is represented by such a box, or the region of a computer's memory in which such a structure is stored is called a cons cell. Every time the `cons` procedure is used, explicitly or implicitly, in the construction of a Scheme value, a new cons cell is allocated, to store information about the car and the cdr. Thus `cons-cell-count` also tallies the number of times `cons` was invoked during the construction of its argument.)

For example, the structure in the following box-and-pointer diagram contains seven cons-cells, so when you apply `cons-cell-count` to that structure, it should return 7. On the other hand, the string `"sample"` contains no cons-cells, so the value of `(cons-cell-count "sample")` is 0.

b. Use `cons-cell-count` to find out how many cons cells are needed to construct the list

```(0 (1 (2 (3 (4)))))
```

See the notes at the end of the lab if you have trouble creating that list.

c. Draw a box-and-pointer diagram of this list to check the answer.

## For Those with Extra Time

If you find that you have extra time, you might want to attempt one or more of the following problems.

### Extra 1: Counting Symbols

Write a procedure, `num-syms`, that counts the number of symbols in a tree of mixed values.

## Notes

### Notes on Exercise 3

In case you don't want to switch documents, here is the code for `sum-of-number-tree`.

```;;; Procedure:
;;;   sum-of-number-tree
;;; Parameters:
;;;   ntree, a number tree
;;; Purpose:
;;;   Sums all the numbers in ntree.
;;; Produces:
;;;   sum, a number
;;; Preconditions:
;;;   ntree is a number tree.  That is, it consists only of numbers
;;;   and cons cells.
;;; Postconditions:
;;;   sum is the sum of all numbers in ntree.
(define sum-of-number-tree
(lambda (ntree)
(if (pair? ntree)
(+ (sum-of-number-tree (car ntree))
(sum-of-number-tree (cdr ntree)))
ntree)))
```

### Notes on Exercise 5

If, for some reason, you are having trouble creating the list

`(0 (1 (2 (3 (4)))))`

try

```(list 0 (list 1 (list 2 (list 3 (list 4)))))
```

## History

Thursday, 16 October 2003 [Samuel A. Rebelsky]

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 Tue Dec 9 13:59:00 2003.
The source to the document was last modified on Thu Oct 16 13:36:04 2003.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003F/Labs/deep-recursion.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu