CSC151 2007S, Class 30: Deep Recursion Admin: * Are there any final questions on the first project report? * I will distribute the second take-home examination on Friday. * You need not look at it until you return from break * I'd like to give those of you who want something academic to do during break an opportunity to start early. * Dr. Davis teaches tomorrow. * Reminder (for those of you who visit class only via EBoard): In person attendance is expected. Overview: * Lists, revisited. * Trees, introduced. * Deep recursion, considered. * Lab. Review: What is a list? * A group of values. * Which typically appear surrounded by parentheses * A sequence of values * A nonempty list is something that you can split into car and cdr * car is geekspeak for "first element" * cdr is geekspeak for "everything but the first element" * A list is a buncha values in a list for * A list is either * An empty list, null BASE CASE * A pair of a value and another list, (cons val lst) * *LISTS ARE DEFINED RECURSIVELY* * Their recursive definition suggests a typical form of recursive proc (define recursive-proc (lambda (lst) ; Base case (if (null? lst) ; matches the BASE CASE for the form of the list SOMETHING (DO_SOMETHING_WITH (car lst) (recursive-proc (cdr lst)))))) IMPORTANT LESSON: The structure of our data often suggests the structure of our recursive (or non-recursive) procedures. LESSON FROM YESTERDAY: Some of the things we build from cons aren't themselves lists. * If the second value is a symbol, then the cons returns a non-list * If there isn't a null at "the end", then its not a list. * If the second parameter to cons is not a list, then cons does not return a list. > (define x (cons 'a 'b)) > x (a . b) > (pair? x) #t > (list? x) #f > (define y (cons 'a x)) > y (a a . b) > (pair? y) #t > (list? x) #f The things that are not lists and that are built from pairs are typically called "trees". * But we like to define them recursively. * A symbol is a kind of tree of symbols * cons of two trees of symbols is a tree of symbols * Alternate description * A symbol is a LEAF in a tree of symbols * cons of two trees of symbols, or a LEAF and a tree of symbols, or a tree of symbols and a LEAF, is a tree of symbols Pattern of recursion on trees: (define recursive-proc (lambda (tree) (if (leaf? tree) ; e.g. (symbol? tree) BASECASE (COMBINE (recursive-proc (car tree)) (recursive-proc (cdr tree)))))) E.g., count the number of symbols (define count-symbols (lambda (tree) (if (symbol? tree) 1 (+ (count-symbols (car tree)) (count-symbols (cdr tree)))))) > (count-symbols (cons abcd abcd)) 8 > (count-symbols (cons 'a null)) . car: expects argument of type ; given () E.g., count the number of times the symbol 'a appears (define count-as (lambda (tree) (if (symbol? tree) (if (eq? tree 'a) 1 0) (+ (count-as (car tree)) (count-as (cdr tree))))))