Quiz 6, CS 257

Name: Barak A. Pearlmutter
CIRT user-id: barak
We trained hard, but it seemed that every time we were beginning to form up into teams, we would be reorganized. I was to learn later in life that we tend to meet any new situation by reorganizing; and a wonderful method it can be for creating the illusion of progress while producing confusion, inefficiency, and demoralization.
- Petronius Arbiter, 210 BC

  1. Write a tail-recursive version of the factorial function fact, which can be defined non-tail-recursively as
    (define (fact n)
       (if (= n 0)
           1
           (* n (fact (- n 1)))))
    
    Hint: use use a helper function of two arguments. (6 points)
    (define (fact n)
      (fact-aux n 1))
    
    (define (fact-aux n a)
      (if (= n 0)
          a
          (fact-aux (- n 1) (* n a))))
    

  2. In the following definitions, some of the open parentheses are followed by a subscript. For each such open parenthesis character, check one box in the corresponding row of the table to indicate whether that open paren begins

    Some of the rows have already been marked for you. (2 points/row = 14 points)

    (aDEFINE (bFLATTEN X)
      (cFLATTEN-AUX X (dLIST)))
    
    (DEFINE (FLATTEN-AUX X Y)
      (eCOND (f(gNULL? X) Y)
             (h(PAIR? X) (iFLATTEN-AUX (jCAR X)
                                       (kFLATTEN-AUX (CDR X) Y)))
             (ELSE (lCONS X Y))))
    
    paren tail-recursive function call non- tail-recursive function call not a function call
    a  X
    b  X
    cX   
    d X  
    e  X
    f  X
    g X 
    h  X
    iX  
    j X 
    k X 
    lX