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"