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"