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