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