Comp 200 Homework 2:
Recursion

Due in class on Mon 11 Feb 2002

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 and paste from this HTML page into DrScheme. You do NOT need to turn in any DrScheme printouts for this problem.

   ;; (doublerA n): number --> number
   ;; Return ...??  (Can you guess, by looking at the code?)
   ;;
   (define (doublerA n)
      (if (zero? n)
          1
          (* 2 (doublerA (sub1 n)))))
   
   
   ;; (doublerB n): number --> number
   ;; Return ...??  (Can you guess, by looking at the code?)
   ;;
   (define (doublerB n)
      (if (zero? n)
          1
          (+ (doublerB (sub1 n))
             (doublerB (sub1 n)))))
   
   
   ;; (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 (add1 (* 3 n))))))
   

   1. Apply the functions doublerA, doublerB, and threes to each of the inputs n = 0, 1, 2, 3, 4 and apply max-of-list to each 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 call, 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).

   2. Now let's try to generalize the numbers you just tallied, to see what we can conclude about the algorithm itself: For other values of n, how many times will doublerA be called? How about doublerB? (The answers are of course expressions involving n.)
   3. 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 about the answer.
      For an input of length n,
      1. what is the smallest number of times that max-of-list could possibly be called?
      2. what is the largest number of times that max-of-list could possibly be called?

3. In class, I explained that Scheme does not have the function ^ defined, rather, the function expt is used for calculating exponents. Write the function ^, which takes in a number x and WholeNum y, and returns x raised to the y power. Write this function without using the function expt, but use expt to check your test cases. Hint: think about the product function we wrote in class.
4. A Fibonacci Sequence is a list of numbers that follows a pattern where the next number in the sequence is the sum of the last two numbers. (i.e. 0, 1, 1, 2, 3, 5, 8, 13, . . .). Write a function fib that takes three WholeNums: a1 and a2, which represent the first two numbers in the sequence, and n, the number of numbers in the sequence; and returns a list that represents a Fibonacci sequence of n numbers, beginning with a1 and a2. You may assume that n cannot be less than 2.
   Example: (fib 0 1 5) = (cons 0 (cons 1 (cons 1 (cons 2 (cons 3 empty)))))
   Hint: You could also write a helper function (fib-help a1 a2 n) that takes the same type of arguments.
5. In class, we talked about structures, and how they could be used for a database. Assume you have a employee database, represented by a list of structures of the following type:

   (define-struct emp (first last id dept salary))
   

   where first, last, and dept are symbols that represent the employee's first name, last name, and department; and id and salary are numbers, that represent the employee id number and his or her salary.
   Data Definition:
   A Database is either
   • empty, or
   • (cons (make-emp symbol symbol number symbol number) Database)
   Here is an example database definition, but you'll probably want to define your own with more entries, to adequately test your functions. You may use one thoroughly-populated database to test all your functions. (Note: list is a function that just makes it easy to create a list, given the elements as input. Example: (list 1 2 3) = (cons 1 (cons 2 (cons 3 empty)))

   (define edb (list (make-emp 'Sam 'Jones 89798 'HR 30000)
                     (make-emp 'Karen 'Chang 49854 'Purchasing 45000)
                     (make-emp 'Sarah 'Smith 38714 'IS 50000)
                     (make-emp 'Omar 'Hernandez 98789 'Internal-Audit 40000))) 
   

   Write the following functions (database queries):
   1. (id->last id db) that takes in a number (representing an id number) and a Database, and returns the last name of the employee with that id number or false of no employee has that id number. (Assume employee id numbers are unique.)
   2. (dept-list dept db) that takes in a symbol (representing a department) and a Database, and returns a list of the id numbers of all employees in that department.
   3. (employee? first-name last-name db) that takes in two symbols (repesenting the first and last name of an employee) and a Database, and returns true if that employee exists in the database and false otherwise.
   4. (dept-salary-total dept db) that takes in a symbol (representing the department) and a Database, and returns the sum of all the individual salaries of the employees within that department.
   5. (dept-salary-check dept sal db) that takes in a symbol (representing the department), and number (that represents a salary) and a Database, and returns true if each and every employee of that department makes less than that salary and false otherwise.
Reminder: In beginner mode, symbols are case sensitive. This is to say (symbol=? 'abc 'Abc) = false. Be careful when writing your test cases.

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?