CSC153.01 2004S, Class 6: List Recursion
Admin:
* Cool convo today. Extra credit!
* Cool panel tonight. Extra credit!
* Extra credit: Usually 1/2 point per activity. Capped at 3 points.
* Homework: Read "Numeric Recursion".
* Homework: HW2: Type checking.
* See below for examples.
* Ask questions Friday and Monday
* Not sure when HW1 will be graded (hopefully Monday).
HW2:
> (type 'a)
symbol
> (type 1)
integer
> (type 1.0)
real
> (type 1/2)
rational
> (type 3+4i)
complex
> (type (list 1 2 3))
list-of-integer
> (type (list 'a 'b 'c))
list-of-symbol
> (type (list 'a 1 "hello"))
heterogeneous-list
> (type type)
procedure
Overview:
* Recursion basics.
* Patterns of recursive functions over lists.
* Lab.
What are the key ideas of recursion?
* It's a mechanism for repetition.
* You call the same procedure on a "subset" of the original input.
* You use the result to compute the solution for the "whole set".
In designing a recursive procedure, you need to think about:
* The return type of the procedure.
* The base case: When the input is 'small enough' to stop recursing.
* How to simplify the input at every step.
* How to use the result in the bigger result.
(define RECURSIVE-PROC
(lambda (PARAM)
(if (SIMPLE-ENOUGH PARAM)
BASE-CASE
(COMBINE PARAM (RECURSIVE-PROC (SIMPLIFY PARAM))))))
For lists
(define RECURSIVE-PROC
(lambda (lst)
(if (null? lst)
BASE-CASE
(COMBINE (car lst) (RECURSIVE-PROC (cdr lst))))))
Example: Sum
(define sum
(lambda (lst)
(if (null? lst)
0
(+ (car lst) (sum (cdr lst))))))
Alternative formulation: Stop when there's one element left
(define RECURSIVE-PROC
(lambda (lst)
(if (null? (cdr lst))
BASE-CASE
(COMBINE (car lst) (RECURSIVE-PROC (cdr lst))))))
(define nonempty-sum
(lambda (lst)
(if (null? (cdr lst))
(car lst)
(+ (car lst) (nonempty-sum (cdr lst))))))
Attempt the lab and ask lots of questions.
* Choosing an appropriate equality test:
+ Parameters are always numbers, use =
+ Parameters are lists and you want to compare contents, too, use equal?
+ Parameters are symbols, use eqv?
+ ...
Reflection
* "Random" details are sometimes hard.
* Need to be careful to consider all the possible cases.
* Preconditions are your friend.
* It takes some time to "get your head around" thinking recursively