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))



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



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



> (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))



> (define (f n)
     (cond ((< n 3) 1)
           (else (+ (f (- n 1)) (f (- n 2))))))
> (f 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)

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) ________________________)


        ((sentence? input) ________________________________________________________)


        (else ________________________________________________________)))

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.