Homework Two
Data Definitions

1. Recursive functions can produce surprising intermediate results during their evaluation. Consider the following three functions

   ;; fact: num -> num
   ;; Return n!, which stands for n*(n-1)*(n-2)*...*3*2*1
   ;;
   (define fact
     (lambda (n)
       (if (zero? n)
           1
           (* n (fact (- n 1))))))
   
   ;; multfib: num -> num
   ;; A multiplicative version of the fibonacci sequence.
   ;;
   (define multfib
     (lambda (n)
       (if (< n 3)
           n
           (* (multfib (- n 1))
              (multfib (- n 2))))))
   
   ;; threes: num -> num
   ;; Returns 1???
   ;;
   (define threes
     (lambda (n)
       (if (< n 2)
           1
           (threes (if (even? n)
                       (/ n 2)
                       (+ 1 (* n 3)))))))
   

   (These functions also appear in the file ~comp210/Assignments/hw02-problem1.ss.)

   Evaluate each of these functions for values of n between 0 and 6 inclusive. For each value of n, use Donkey to determine the total number of calls made to each function. (The initial call counts, so the answer for n = 0 is 1 in each case.)

   For a small amount of extra credit, estimate the number of recursive calls made by each function in terms of n. (Warning: I don't know the answer for threes.)

2. Designing list-handling programs.
   Recall the recipe for writing functions.
   1. Write any pertinent data definitions (e.g., a List-Of-Numbers).
   2. Write sample inputs meeting that data definition.
   3. Derive a template for a generic function (e.g., handle-lon).
   4. Give the contract (the types of inputs and outputs), and description (as needed).
   5. Sample test cases (presumably based on your sample inputs).
   6. Fill in the template to get a working program.
   7. Test your program on the sample inputs.
   Do all of these steps inside DrScheme comments, except #4 and half of #5. Use this design recipe for the following programs. (If one part is the same as a previous answer, just refer to your previous answer.)
   1. A function total which returns the sum of the numbers in the list.
   2. A function all-positive? which returns true iff the list list contains only positive numbers.
   3. A function count-positives which returns the number of positive numbers in the list.
   4. A function positive-part which returns a list of numbers: all the positive numbers in the input list.

3. An Association is (cons key (cons datum null)), where key is a symbol and datum is any Scheme value.

   Define an Association List (i.e., a list of Associations). Using the design recipe, write the function lookup, which takes a symbol and an Association List. It searches the association list until it finds an association whose key is the same as its first argument. If it finds such an association, it returns the second element of the association. If not, it returns¹ #f.