Exam#1 Solutions -- Problem 4

1998 Spring

(20pts) Write the function max, which takes a non-empty list of numbers, and returns the largest number in the list. Use an accumulator, and do not use local. Show the (recursive) calls to your function(s) that occur in the hand-evaluation of (max (list 7 5 9 2)).

Be sure to include a contract and description for all functions you write. (You don't need to write any data description for this problem, though you are welcome to.)

;; max: non-empty list of numbers --> number
;; Return the maximum element of the list.
;;
(define max
  (lambda (nelon)
    (max-helper (rest nelon) (first nelon))))

;; max-helper: list-of-numbers, number --> number
;; Return the maximum of any number in the list, and max-so-far
;;
(define max-helper
  (lambda (lon max-so-far)
    (if (null? lon)
        max-so-far
        (max-helper (rest lon) (bigger-of-two (first lon) max-so-far)))))


;; bigger-of-two: number,number --> number
;; Given to numbers, return the larger.
;;
(define bigger-of-two
  (lambda (a b)
    (if (>= a b)  a  b)))

You are welcome to use local to keep max-helper accessible only inside max.

If you like, this problem can be also done without defining bigger-of-two, including the if-statment inside the code of max-helper. (Which version do you feel reads better, aesthetically?)

For the hand-evaluation of the recursive calls,

  (max (list 7 5 9 2))
= (max-helper (list 5 9 2) 7)
= (max-helper (list 9 2)   7)
= (max-helper (list 2)     9)
= (max-helper (list)       9)
= 9