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