Comp 200 hw02: Recursion

Due in class 01.Feb.07 (Wed)

1. Consider this simple function, which takes two numbers, and returns the maximum of those two:

   ;; (max2 a b): number, number --> number
   ;;
   (define (max2 a b)
     (if (> a b)
         a
         b))
   

   1. Write max3, which takes three inputs and returns the largest; write this without calling another function like max2. (Hint: use an if statement nested inside another if.)
   2. Write max4, which takes four numbers as input. This time, make use of the functions max2 and/or max3 you just wrote and tested!
2. We'll observe the behavior of the following recursive functions. (You can cut-paste from the file ~comp200/hw02.ss, which also includes test cases.)

   ;; (doublerA n): number --> number
   ;; Return ...??  (Can you guess, by looking at the code?)
   ;;
   (define (doublerA n)
      (if (zero? n)
          1
          (* 2 (doublerA (- n 1)))))
   
   
   ;; (doublerB n): number --> number
   ;; Return ...??  (Can you guess, by looking at the code?)
   ;;
   (define (doublerB n)
      (if (zero? n)
          1
          (+ (doublerB (- n 1))
             (doublerB (- n 1)))))
   
   
   ;; (max-of-list nums): non-empty-list-of-number --> number
   ;; Return the largest number in nums.
   ;;
   (define (max-of-list nums)
       (if (empty? (rest nums))
           (first nums)
           (if (> (first nums) (max-of-list (rest nums)))
               (first nums)
               (max-of-list (rest nums)))))
   
   
   ;; (threes n) : number --> 1?
   ;; A strange function:
   ;; Starting with n, next go to either n/2 (if n even) or 3n+1 (if n odd).
   ;; Stop when we reach 1.
   ;; Will we always stop, though?
   ;;
   (define (threes n)
     (if (<= n 1)
         1
         (if (even? n)
             (threes (/ n 2))
             (threes (+ (* 3 n) 1)))))
   

   Apply doublerA, doublerB, threes to each of the inputs n=0,1,2,3,4. For max, use the following inputs:

   (cons 4 empty)
   (cons 3 (cons 4 empty))
   (cons 4 (cons 3 empty))
   (cons 2 (cons 3 (cons 4 empty)))
   (cons 4 (cons 3 (cons 2 empty)))
   (cons 1 (cons 2 (cons 3 (cons 4 empty))))
   (cons 4 (cons 3 (cons 2 (cons 1 empty))))
   (cons 1 (cons 4 (cons 2 (cons 3 empty))))
   

   For each function, write down:
   1. the result of the function call, and
   2. the number of times the function was called. (The initial call counts, so for n=0 the answer is 1 in each case.) To determine how many times the function is called, you can use your noodle, and then try checking with the stepper (counting how many times the function-name is at the front of the highlighted about-to-be-evaluated part).

   Now let's try to generalize the numbers you just tallied, to see what we can conclude about the algorithm itself:

   3. For other values of n, how many times will doublerA be called? How about doublerB? (The answers are of course expressions involving n.)
   4. How about max-of-list, for lists of length n? This is a bit problematic, because (as shown) different lists of the same length can produce a different number of recursive calls. But let's try to see what we can say the answer: For an input of length n,
      1. what is the smallest number of times that max could possibly be called?
      2. what is the largest number of times that max could possibly be called?
3. Write the funciton product, which takes in a list of numbers, and returns the product of the numbers in the list.
4. Recall our definition: A list-of-numbers is either
   • empty, or
   • (cons number list-of-numbers).
   We've seen that functions which handle lists-of-numbers tend to have a shape similar to the shape of the above definition:

   (define (fun-for-number-list lon)
      (if (empty? lon)
          ...
          ...(first lon)...(fun-for-number-list (rest lon))...)))
   

   The only place where functions handling list-of-numbers vary from each other is in how they fill in the dots.

   This problem deals with taking lists of words (symbols), and handling any foreign words encountered. For this problem, cut-and-paste the following helper function:

   (define some-french-words
     (list 'bon 'jour 'bonjour 'bonbon 'toujours 'gateau 'chat 'chats
           'soliel 'lune 'mer 'ooh-la-la 'le 'la 'monde 'tout 'toutes))
   
   (define some-italian-words
     (list 'ciao 'bella 'madonna 'donna 'vermicelli))
   
   (define some-german-words
     (list 'achtung 'sonne 'ausgezeichnet 'wienerschnitzel 'bleistift 'gesundheit))
   
   (define some-other-words
     (list 'sauna     ; Finnish
           'sinasappelsap  ; dutch: chinese-apple juice  = orange juice
           'pindakaas      ; dutch peanut-cheese is really peanutbutter.
           'aloha 
           'tsunami 'domo 'aragoto  'hai 'haiku
           'ninavut))
   
   
   (define non-english-words
     (append some-french-words
             some-italian-words
             some-german-words
             some-other-words))
   
   ;; foreign? : symbol --> boolean
   ;; Is the given word non-english?
   ;;
   (define (foreign? wrd)
     (contains? non-english-words wrd))
   
   
   (define sentence0 empty)
   (define sentence1 (list 'orange 'bonbon 'eat 'wienerschnitzel 'haiku))
   (define sentence2 (list 'ooh-la-la))
   
   

   Write the following four functions, which each take a list of symbols as input:
   1. all-foreign?, which returns true if all the symbols are words in a non-english language, and false otherwise.
   2. number-of-foreign, which returns how many non-english words occur in the list.
   3. collect-foreigns, which itself returns a list, consisting of all the words which are foreign.
   (Before proceeding, double-check with yourself that you're sure what the output should be when the input is, say, the list containing 'orange 'bonbon 'eat 'haiku 'and 'wienerschnitzel. or just empty.)

   Hint: To write the functions, think recursively, mirroring the definition of list-of-numbers. The relevant questions are:

   1. What is the gloxnard¹ of empty?
   2. For lists that aren't empty (i.e. that have a first and a rest), if you magically knew the gloxnard of the rest of the list, how would you compute the gloxnard of the entire list?

The (new, improved) Design Recipe

1. First, write down the function header:
   1. comments about what the function takes in and returns.
   2. what it returns (answer ``what'', not ``how'').
   3. the define (a bit of actual code),
      
2. Write down test cases: actually call your to-be-written function on sample inputs.
3. Now some more rote work after the header we wrote earlier. For complicated data (like List-of-Numbers), look at the definition: There were two types of lists, so the function needs to ask which type it has;
4. Now we can even refine each of these (two) cases (empty, cons), writing down the sub-parts in each case (if any).
5. Finally, for any of these sub-parts which happen to be themselves valid inputs for the function we're writing, consider the natural recursive call (the one reflecting the definition's recursion). Ask yourself what type of thing those pieces are. (This is the gloxnard bit emphasized earlier.)
6. Okay, now the creative part: given the parts from the previous step, how do we piece them together to get our answer?
7. Finally, test your function by pressing execute and inspect the results.