Recitation #7, Wed., 9/10/97

EXAMPLE 1: The "factorial" of an nonnegative integer n is written: n!  and
is defined to be
                       n * (n-1) * (n-2) * ... * 1.
The useful facts
       n! = n * (n-1)!
       0! = 1   by convention,
lead to a recursive procedure:

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))



EXAMPLE 2: The value of (sum-square n) is supposed to be 
                     n^2 + (n-1)^2 + ... + 1^2 + 0^2.
A recursive version was given in lecture.  Here is a tail-recursive
definition of sum-square:

(define (sum-square n)
  (define (loop sum i)
    (if (> i n)
	sum
	(loop (+ (square i) sum) (+ i 1))))
  (loop 0 0))

(define (square x) (* x x))


IN CLASS PROBLEM:

Ben Bitdiddle has defined a procedure, p, which takes a number argument
and returns a truth value.  Your job is to define a procedure find-min
with the property that, for any integer n, the value of
                (find-min n)
is the SMALLEST INTEGER, k, such that
        (i)  k >= n, and
        (ii) the value of (p k) is true.

For example, if Ben had written
        (define (p k) (<= 100 k))            ;<= is the `less-than-or-equal-to' test
then you could do your job by writing
        (define (find-min n)
          (if (<= n 100) 100 n))

(1) Suppose Ben had written
        (define (p k) (even? k))
Complete the following:
        (define (find-min n) <??>)

SOLN:  if n is even, (p n) is #t, so (findmin n) is simply n.
       if n is odd, then (p n) is #f, but p applied to n+1 is #t, so
       (findmin) is n+1.
       Here's a Scheme definition which behaves this way:

      (define (findmin n)
       (if (even? n) n (+ n 1)))