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