Fundamentals of Computer Science I (CS151.02 2007S)
[Skip to Body]
Primary:
[Front Door]
[Syllabus]
[Glance]
[Search]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Projects]
[Readings]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151 2006F (Rebelsky)]
[CSC151.01 2007S (Davis)]
[CSCS151 2005S (Stone)]
This lab is also available in PDF.
Summary: In this laboratory, you will further explore issues of deep recursion introduced in the reading on pairs and pair structures and continued in the reading on deep recursion.
Contents:
a. Make sure that you have the reading on pairs and pair structures and the reading on deep recursion open in separate tabs and windows.
b. Make sure that you have a piece of paper and writing instrument handy.
Recall that a list is a data structure defined recursively as follows:
In
the reading on pairs and pair structures,
the section entitled Recursion with Pairs
includes a procedure
that works on number trees
, nested structures built with the
pair
procedure.
Write a recursive definition for number trees, trees built from only numbers and cons cells, similar to that for lists.
Using your recursive definition of number trees from the previous probelm,
write a procedure, (numbertree? val)
that returns
true if val is a number tree and false otherwise.
Consider again the sumofnumbertree
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.
(sumofnumbertree (cons (cons (cons 0 1) (cons 2 3)) (cons (cons 4 5) (cons 6 7))))
b. What do you expect sumofnumbertree
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 sumofnumbertree
to return when
given the empty list as a parameter? Verify your answer experimentally.
f. What do you expect sumofnumbertree
to return when
given (list 1 2 3 4 5)
as a parameter? Verify your answer
experimentally.
a. What preconditions should sumofnumbertree
have?
b. Use the numbertree?
predicate from earlier to rewrite
sumofnumbertree
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 sumofnumbertree
so that it checks
for and reports errors only when it is at one of the nonpair values.
a. Define and test a procedure named conscellcount
that takes
any Scheme value and determines how many boxes would appear in its
boxandpointer 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 conscellcount
also tallies the number
of times cons
was invoked during the construction of its
argument.)
For example, the structure in the following boxandpointer diagram
contains seven conscells, so when you apply conscellcount
to that structure, it should return 7. On the other hand, the string
"sample"
contains no conscells, so the value of
(conscellcount "sample")
is 0.
In answering this question, you should consider whether each value, in
turn, is a pair using the pair?
predicate.
b. Use conscellcount
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 boxandpointer diagram of this list to check the answer.
If you find that you have extra time, you might want to attempt one or more of the following problems.
As you may recall, a tree is either (a) a nonpair value or (b) the cons of two trees. In the reading, you saw a procedure that counted the number of values in a tree. In this lab, you wrote a procedure that counted the number of cons cells (pairs) in a tree. What is the relationship between the numbers returned by those two procedures?
Write a procedure, (treemember? sym treeofsymbols)
, that
determines whether sym
appears anywhere in
treeofsymbols
.
In case you don't want to switch documents, here is the code for
sumofnumbertree
.
;;; Procedure: ;;; sumofnumbertree ;;; 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 sumofnumbertree (lambda (ntree) (if (pair? ntree) (+ (sumofnumbertree (car ntree)) (sumofnumbertree (cdr ntree))) ntree)))
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)))))
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/History/Labs/deeprecursion.html
.
[Skip to Body]
Primary:
[Front Door]
[Syllabus]
[Glance]
[Search]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Projects]
[Readings]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151 2006F (Rebelsky)]
[CSC151.01 2007S (Davis)]
[CSCS151 2005S (Stone)]
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 Thu Sep 13 20:54:17 2007.
The source to the document was last modified on Mon Mar 12 21:08:29 2007.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2007S/Labs/deeprecursion.html
.
You may wish to validate this document's HTML ; ;
Samuel A. Rebelsky, rebelsky@grinnell.eduhttp://creativecommons.org/licenses/bync/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.