CSC151.02 Class 29, Deep Recursion Admin * Where is Michael? * No class Friday. * Have a great break. * Reading for break: Vectors Overview * What is a list? Revisited * What does list recursion look like? * Alternate structure: The tree * Recursing over trees * Two examples * Lab /What is a list?/ * Billups: A collection of elements * Poythress: Null or Cons of a value and another list * Observation: The MLP definition is recursive /How do we recurse over lists?/ * Either do something with the null list * Or combine the first element with a recursive call to the remainder /A new data structure: The tree/ * A tree is either (1) a simple value (number, string, character, procedure, boolean, symbol) or (2) the cons of two trees * For example, here is a tree of numbers (see the real board) * Note that lists that contain other lists are a form of tree. /A New Form of Recursion/ * Since these structures are recursive in both the car and the cdr, procedures that manipulate them might also recurse over the car and the cdr. * Example: Summing all the values in one of these things that only contains numbers. (define sum-of-number-tree (lambda (tree) ; If it's just a simple value, use that value (if (not (pair? tree)) tree (if (null? (cdr tree)) ; Sum everything in the left subtree (sum-of-number-tree (car tree)) (let ( ; Sum everything in the left subtree (left-sum (sum-of-number-tree (car tree))) ; Sum everything in the right subtre (right-sum (sum-of-number-tree (cdr tree)))) ; Put 'em together (+ left-sum right-sum)))))) A related intertesting problem: Finding the depth of a tree: The longest number of steps to take to reach a non-pair. * Determine when we hit the base case * Not a pair * Determine what the value should be in the base case * 0 * How do we simplify the problem? * Take the car (the left subtree) * Take the cdr (the right subtree) * How do we use the resutl of recursing on the simplified value? * Suppose we know the depth of the left subtree and the depth of the right subtree, what is the depth of the whole tree? * 1 + max * Turn it all into Scheme (define depth (lambda (tree) (if (not (pair? tree)) 0 (+ 1 (max (depth (car tree)) (depth (cdr tree))))))) What is the "pattern" which we use for tree recursion? (define PROCEDURE (lambda (tree) (if (not (pair? tree)) BASE-CASE (let ((left (PROCEDURE (car tree))) (right (PROCEDURE (cdr tree)))) (COMBINE left right))))) depth * PROCEDURE: depth * BASE-CASE: 0 * COMBINE: + 1 max (define depth (lambda (tree) (if (not (pair? tree)) 0 (let ((left (depth (car tree))) (right (depth (cdr tree)))) (+ 1 (max left right)))))) A number tree is a tree in which all the non-pairs are numbers Write number-tree? PROCEDURE: number-tree? BASE-CASE: number? COMBINE: and (define number-tree? (lambda (tree) (if (not (pair? tree)) (number? tree) (let ((left (number-tree? (car tree))) (right (number-tree? (cdr tree)))) (and left right)))))