Quiz 6, CS 257

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
   • a tail-recursive function call
   • a non-tail-recursive function call
   • not a function call

   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
   c	X
   d		X
   e			X
   f			X
   g		X
   h			X
   i	X
   j		X
   k		X
   l	X