Programming Concepts Midterm #3: Recursion Excursion

0. (0 points) NAME___________________________________ PERIOD _______

INSTRUCTIONS

• Write your name on the test. If you can't remember your name, it will cost you a point.
• This test is closed book. No computer, no friends, no Internet. Just you, your brain, your pen(cil), and the paper.
• Calculators are not permitted. Not even the really big calculators in the classroom.
• Where possible, SHOW YOUR WORK! (It is really hard to give partial credit if you don't!)
• Do not write programs that worry about checking for errors. You may assume that all arguments to a function will be in the function's domain.
• With the exception of problem #3, you can write helper functions.
• Don't panic. It's just a test.

1. (5 points; 1 point each) What will the EXACT output be for each of the following pieces of code? (Don't bother with output for the defines; they are there for the other stuff.

> (appearances 'y '(yeah youre all gonna be in this experimental film))

0   ;; The word 'y is not in the sentence



> (keep (lambda (x) (member? 'a x)) '(go hang a salami im a lasagna hog))

(hang a salami a lasagna)



> (define (f a b)
     (cond ((> a b) 1)
           (else (* a (f (+ a 1) b)))))
> (f 3 5)

60




> (define (mystery p? s)
     (cond ((empty? s) ())
           ((p? (first s)) (se (first s) (mystery p? (bf s))))
           (else (mystery p? (bf s)))))
> (mystery number? '(one 2 three 4 5 six))

(2 4 5)



> (define (f n)
     (cond ((< n 3) 1)
           (else (+ (f (- n 1)) (f (- n 2))))))
> (f 5)

5

2. (5 points) (Noa Shadmon, Julia Nelson) If Mr. Bell could cut his consumption of caffeinated products, it would improve his health.

Despite being a math teacher, the only time he uses numbers in sentences is when he discusses his eating habits. Help Mr.Bell by writing the decaffeinate function, which takes a sentence uttered by Mr. Bell and chops the amount of caffeinated foods in half.

You can write a helper function if you wish, but the decaffeinate function MUST be written recursively.

> (decaffeinate '(must quaff 22 cans of Pepsi))
(must quaff 11 cans of Pepsi)
> (decaffeinate '(demand 4 chocolate bars and 16 bottles of Mexican Coke))
(demand 2 chocolate bars and 8 bottles of Mexican Coke)
> (decaffeinate '(drink 7 cups of tea))
(drink 3.5 cups of tea)
> (decaffeinate (i hate coffee)
(i hate coffee)


(define (decaffeinate sent)
  (cond ((empty? sent) sent)
        ((number? (first sent)) 
         (se (/ (first sent) 2.0) (decaffeinate (bf sent))))
        (else (se (first sent) (decaffeinate (bf sent))))))

3. (5 points) The function reversi takes a sentence of words and returns a sentence containing the reverses of the words in reverse order. It also can take a word as its input and return the word in reverse order.

> (reversi '())
()
> (reversi 'dunbar)
rabnud
> (reversi '(alpha beta gamma))
(ammag ateb ahpla)

Fill in the blanks to write reversi. For this problem, you may NOT write any helper functions.

(define (reversi input)


  (cond ((empty? input) input)


        ((sentence? input) (se (reversi (bf input)) (reversi (first input))))


        (else (word (reversi (bf input)) (first input)))))

4. (5 points) The function rest-of-word takes a letter and a word as its arguments and returns the rest of the word, starting with the first instance of the letter. If the letter does not appear in the word, rest-of-words returns #f.

> (rest-of-word 'a 'hippogriff)
#f
> (rest-of-word 'f 'inflammable)
flammable
> (rest-of-word 'a 'fairway)
airway

You can write a helper function if you wish.

(define (rest-of-word letter wd)
  (cond ((empty? wd) #f)
        ((equal? (first wd) letter) wd)
        (else (rest-of-word letter (bf wd)))))