Lab Quiz, Foundations of Computing, Week 7 -- Tues Nov 7 2000

This definition is executed:

;; Like Scheme reverse
(define (rev lst)
  (if (null? lst)
      '()        
      (append (rev (cdr lst)) (list (car lst)))))

Then this expression is typed into the Scheme interpreter and evaluated. It returns the result shown:

> (rev '(x y z))
(z y x)

The following questions all concern what happens when the expression (rev '(x y z)) is evaluated. It may be helpful to imagine what you would see if you traced the execution of rev and append.

1. What is the base case in this example?
   
   
   
2. How many times is rev called?
   
   
   
3. What is lst bound to when rev is called the first time?
   
   
   
4. What is the value of (cdr lst) when rev is called the first time?
   
   
   
5. What is the value of (rev (cdr lst)) when rev is called the first time?
   
   
   
6. What is the value of (car lst) when rev is called the first time?
   
   
   
7. What is the value of (list (car lst)) when rev is called the first time?
   
   
   
8. What is the value of (append (rev (cdr lst)) (list (car lst))))) when rev is called the first time?