CSC151 2009F, Class 2^5: Numeric Recursion

Admin:
* Exam 2 distributed.  Due next Wednesday.
* No office hours today.  
  * I should be available via email today and tomorrow.
* Preregistration is coming up.  
  * I encourage you to consider going on in CS.  
  * The natural next course is CSC 161.  
  * A few of you have special circumstances, and should discuss them with me.
* Technological impact of Grinnell, claimed by Tony Stubblebine ('01 or so)
  "[T]he twitter guys all got a demo of GrinnellPlans early on and the 
   @messages feature is partially based on quicklove."

Overview:
* About the exam.
* Named Let.
* Recursion, Generalized.
* Thinking About Natural Numbers.
* Numeric Recursion.
* Lab.

Named Let: A (somewhat strange) mechanism for writing local recursive helpers

(letrec ((NAME (lambda (params) BODY)))
  ...)a

(define last
  (letrec ((last-kernel
            (lambda (lst)
              (if (null? (cdr lst))
                  (car lst)
                  (last-kernel (cdr lst))))))
    (lambda (lst)
      (cond
        ((null? lst)
         (error "Cannot find the last element of an empty list"))
        ((not (list? lst))
         (error "Cannot find the last element of a non-list"))
        (else
         (last-kernel lst))))))$a
Observation: 
* We often want just one local recursive procedure (e.g,. a kernel)
* Choose a new way of writing that one local recursive procedure which is
  * Clear to experienced programmers
* What goes in a recursive procedure definition?  (And the first call to
  that procedure)
  * Name
  * Parameters
  * Body
  * First call, which associates values with the parameters

* [Standard structure of a recursive procedure over lists]
  * conditional
  *(recurse (cdr lst))

Named let

(let NAME ((PARAM1 VAL1)
           (PARAM2 VAL2)
           (PARAM3 VAL3))
  BODY)
  
(define last
  (lambda (lst)
    (cond
      ((null? lst)
       (error "Cannot find the last element of an empty list"))
      ((not (list? lst))
       (error "Cannot find the last element of a non-list"))
      (else
       (let kernel ((remaining lst))
         (if (null? (cdr remaining))
             (car remaining)
             (kernel (cdr remaining))))))))


(define len
  (lambda (lst)
    (cond
      ((not (list? lst))
       (error "Cannot find the last element of a non-list"))
      (else
       (let kernel ((so-far 0) (remaining lst))
         (if (null? remaining)
             so-far
             (kernel (+ 1 so-far) (cdr remaining))))))))