RECURSIVE PRACTICE PROBLEMS -- (Some borrowed from TA Lisa)

UPDATED since section –- I fixed some errors and added more examples. Updates are in bold font.

The following exercises are intended to help you solidify your grasp of recursion. The problems start out easy and get progressively more difficult – you should work through as many as you can, and you should definitely understand/be able to do all of them before the midterm. Try to give both an embedded and a tail recursive solution (if possible). Note that you should never use higher-order functions (like every) and you should try to use as few regular procedures as possible. Also, assume that you will be given proper (though possibly empty) input – e.g. if you procedure expects a sentence of numbers, you can assume that you will get a (possibly empty) sentence of numbers.

You’ll need another sheet of paper.

EASY:

1. For each of the basic Recursive Patterns ( MAPPING, FINDING, COUNTING, FILTERING, TESTING, and COMBINING), give the following:

a. In your own words, describe the ‘essential feature’ of the pattern (i.e. that which makes the pattern different from all the others.

b. Create your own example of a problem that fits into the pattern – it should be a problem that you haven’t seen before.

c. Give both an embedded and a tail-recursive (if possible) solution to the problem.

d. Find the person next to you, and try to solve the example problem that they came up with for this pattern. Try to make your solution as similar as possible to your solution for your own problem from part c.

HARD:

2. (define (number-everything sent)): What it does: returns the same sent, but with the position number and a colon prefixed to each. E.g. (number-everything ‘(im a sentence))=>(1:im 2:a 3:sentence); (number-everything ‘(dog cat))=>(1:dog 2:cat)

3. (define (wave-maker valley peak cycles)): What it does: counts up from the valley number to the peak number and then back down for the number of cycles). E.g. (wave 1 3 2)=> 123321123321; (wave 1 1 5)=>11111 or (wave 1 1 5)=> 1111111111 or (wave 1 1 5)=>””; use whichever case is easiest for your implementation; (wave 3 6 5)=> 3456654334566543345665433456654334566543.

4. (define (partition-count pivot sent)): What it does: returns a sentence of three values: the number of items in sent that are less than pivot, the number that are equal to pivot, and the number that are greater than pivot. E.g. (partition-count 5 ‘(4 9 3 5 5 6 3))=> (3 2 2); (partition-count 2 ‘(1 2 1))=> (2 1 0))

5. (define (partition pivot sent)): Like #3, but actually partitions the sentence (instead of just returning the number of elements in each partition) where all of the items that are less than the pivot come first, then all of those that are equal, then all of those that are E.g. (partition 5 ‘(4 9 3 5 5 6 3))=> (4 3 3 5 5 9 6); (partition 5 ‘(2 8 5 4 1 7 9 5 3)) = ‘(2 4 1 3 5 5 8 7 9)

6. (define (sum-of-n-powers n pow)): Returns the sum of the first n numbers (starting with n), each raised to the pow power. E.g. (sum-of-n-powers 4 4)=> 354 [Because 1^4+2^4+3^4+4^4= 354]; (sum-of-n-powers 2 2)=> 5 [1^2 + 2^2 = 5]

7. (define (exactly-n-a-words? n sent)): Returns #t only if the sent contains exactly n words that start with the letter a. (It will be helpful to use the a-word? predicate.) E.g. (exactly-n-a-words 5 ‘(an angry but apologetic apothecary asked me for his money))=>#t; (exactly-n-a-words 3 ‘(apples oranges apples apples apples))=>#f

8. (VERY HARD!) (define (adds-to-n n sent)): Returns #t only if there is a subset of numbers in the sentence that add to n. E.g. (adds-to-n 7 ‘(3 2 6 3 99 1))=> #t [because 1+6=7]; (adds-to-n 10 ‘(1 2 5 6))=>#f [cuz there is no way to make 10 using only those elements]; (adds-to-n 10 ‘(1 2 10 3))=>#t. [[Hint: This illustrates another use of recursion: to try out possible answers and then discard/keep some or all of them. When you look at each element in the sentence, you know that it is either in the subset of things that adds to n or it is not. If it is, what should your recursive call (on the remaining sentence) be? If it is not, what should your recursive call be?

9. (define (supercensor sent banned_list)): Just like the censor from lab, but will also bleep out words if they are spelled backwards in the sent. E.g. (supercensor ‘(the quick brown dog jumped) ‘(quick god party)) = ‘(the bleep! brown bleep! jumped) [[Note: there are several ways to do this. You should not do it by first reversing all the words in the banned_list and calling normal censor – you should (at each recursive step) see if the word is the same, forwards or backwards.]]

CAVEAT: These problems are not supposed to be exhaustive (or even illustrative) of all the things you may see on the midterm.