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))))))