CSC151 2007S, Class 14: Recursion with Natural Numbers (1)

Admin:
* HW7 is now due on Friday.  I have not completely 
  updated the syllabus to reflect this change.
* We will be continuing the numeric recursion lab tomorrow, 
  so you might choose to reread Numeric Recursion.
* You should also do a new reading on Writing Recursive Procedures.
* Yay School Delays!
  * But there are no snow days at Grinnell College

Overview:
* Writing Recursive Procedures.
* Short Introduction to Numeric Recursion.
* Lab.

/Recursive Procedures/

(define RECURSIVE_PROC
  (lambda (PARAMS)
    (if (TEST_FOR_SIMPLICITY PARAMS)
        (BASE_CASE)
	(COMBINE (EXTRACT_SIMPLE_VALUE PARAMS)
	         (RECURSIVE_PROC (SIMPLIFIED PARAMS))))))
		 
(define RECURSIVE_PROC
  (lambda (PARAMS)
    (cond
      ((TEST_FOR_SIMPLICITY PARAMS)
       (BASE_CASE))
      ((TEST_FOR_MAIN_CASE PARAMS)
       (COMBINE (EXTRACT_SIMPLE_VALUE PARAMS)
                (RECURSIVE_PROC (SIMPLIFIED PARAMS))))
      (else (RECUSRIVE_PROC (SIMPLIFIED PARAMS))))))

Example: Selecting all numbers from a list
		 

(define just-numbers
  (lambda (a)
    (cond
      ((null? a)
       null)
      ((number? (car a))
       (cons (car a)
             (just-numbers (cdr a))))
      (else (just-numbers (cdr a))))))

For lists
  TEST_FOR_SIMPLICITY is almost always null?
    Sometimes (null? (cdr a))
  SIMPLIFY is almost always CDR
  EXTRACT is almost always CAR

When the thing we're recursing over is a number
  TEST_FOR_SIMPLICITY is almost always zero?
    Sometimes it is (= a 1)
    Sometimes it is (= a SOME_LARGE_NUMBER)
  SIMPLIFY is almost always "subtract 1"
  EXTRACT is almost always "use the current value of a"