Computer Science Fundamentals (CS153 2004S)

Local Procedures and Recursion

Summary: In this laboratory, we consider the various techniques for creating local recurs ive procedures, particularly letrec and named let. We also review related issues, such as husk-and-kernel programming.



Exercise 0: Preparation

a. Review the corresponding notes on letrec and named let.

b. Start DrScheme.

Exercise 1: Alternating Lists

A non-empty list is an s-n-alternator if its elements are alternately symbols and numbers, beginning with a symbol. It is an n-s-alternator if its elements are alternately numbers and symbols, beginning with a number.

Write a letrec expression in which

Your letrec expression should have the form

  ((s-n-alternator? ...)
   (n-s-alternator? ...))

Note: By mutually recursive, we mean two procedures that call each other.

Exercise 2: Iota, Revisited

As you may recall, Iota takes a natural number as argument and returns a list of all the lesser natural numbers in ascending order.

a. Define and test a version of the iota procedure that uses letrec to pack an appropriate kernel inside a husk that performs precondition testing. This version of iota should look something like

(define iota
  (lambda (num)
    (letrec ((kernel ...))

b. Define and test a version of the iota procedure that uses a named let. This version of iota should look something like

(define iota
  (lambda (num)
    (let kernel (...) 

Exercise 3: Taking Some Elements

Define and test a procedure, (take lst len), returns a list consisting of the first len elements of the list, lst, in their original order.

The procedure should signal an error if lst is not a list, if len is not an exact integer, if len is negative, or if len is greater than the length of lst.

Exercise 4: Intersection

a. Define and test a procedure (intersection left right) that takes two lists of symbols as arguments and returns a list of which the elements are precisely those symbols that are elements of both left and right.

b. What does your procedure do if a symbol appears in both lists and appears more than once in one or both of the lists?

For Those with Extra Time


No notes yet.



Monday, 24 October 2000 [Samuel A. Rebelsky]

Wednesday, 14 March 2001 [Samuel A. Rebelsky]

Tuesday, 15 October 2002 [Samuel A. Rebelsky]

Tuesday, 4 February 2003 [Samuel A. Rebelsky]

Wednesday, 4 February 2004 [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 Fri May 7 09:44:18 2004.
The source to the document was last modified on Thu Feb 5 10:47:28 2004.
This document may be found at

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

Samuel A. Rebelsky,