Programming Concepts Midterm #3: Recursion Excursion

0. (0 points) NAME___________________________________ PERIOD _______


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)
> (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)
> (rest-of-word 'f 'inflammable)
> (rest-of-word 'a 'fairway)

You can write a helper function if you wish.