6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology This message we will repeat many times during the term. The structure of the procedure tends to go hand-in-hand with the structure of the data abstraction it is designed to manipulate Slide 31.2.9 countleaves and substitution model Because this is a new kind of data structure. and because we are creating new kinds of procedures to manipulate them, let's look (define (coun reel 1)/base cas at this a bit more carefully. Here again is the code for count 【(1eaf els leaves. with the two base cases. and the double recursion (countleaves (edr tree)) down the first branch and the rest of the branches of the tree ine (leaf not《pair?x))) 91200 600SC countleaves and substitution model Slide 31.2.10 Let's use our substitution model to see how this procedure evolves, and we will do this in stages. Here is the simplest case recursive case veg (car tr Let's apply count-leaves to a tree of one leaf. To be very careful, I am going to replace (list 2)with the define(e△E?x) actual box-and-pointer structure that is its value Count-leaves first checks the base cases but neither applies. Thus it reduces to adding count-leaves of the (count leaves (2)) 9 ((oount leaves 2)(oountleaves nil)) first subtree, or the car of the box-and-pointer structure to 6001 SKP soa count-leaves of the rest of the branches, or the cdr or the box-and-pointer structure Note that the first recursive call will catch the second base case while the second recursive call will catch the first base case, and eventually this reduces to the correct value for the number of leaves in this tree, as seen in the original box and pointer diagram, which had exactly one element in it Slide 31.2.11 countleaves and substitution model- pg 2 Now let's try a bit more complicated tree, as shown. Notice that this tree has the property that its first branch is just a leaf, but its define (countleaves tree) ((null? tree) 0),base case ((leaf? tree) 1) second branch, defined as everything but the first branch, is recursive case itself a tree (countleaves (odr tree))))) Count-leaves thus applies to the box-and-pointer ( define(Ie△f?x) (not (pair? x))) structure shown. In this case. the recursive call will add the number of leaves in the first branch, which is just the leaf, 5 since that is what the car returns to the number of leaves in es5) oount⊥ayes the tree, (7)since that is what the cdr of the original structure returns hus the first recursive call will trigger the second base case returning 1 for the single leaf there The second recursive call will reduce to the case we saw on the last slide recognizing this as another tree. Thus it unwinds the tree one more level then returning i for the leaf in the first branch, and o for the empty tree in the second branch
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. This message we will repeat many times during the term. The structure of the procedure tends to go hand-in-hand with the structure of the data abstraction it is designed to manipulate. Slide 31.2.9 Because this is a new kind of data structure, and because we are creating new kinds of procedures to manipulate them, let's look at this a bit more carefully. Here again is the code for countleaves, with the two base cases, and the double recursion down the first branch and the rest of the branches of the tree. Slide 31.2.10 Let's use our substitution model to see how this procedure evolves, and we will do this in stages. Here is the simplest case. Let's apply count-leaves to a tree of one leaf. To be very careful, I am going to replace (list 2) with the actual box-and-pointer structure that is its value. Count-leaves first checks the base cases, but neither applies. Thus it reduces to adding count-leaves of the first subtree, or the car of the box-and-pointer structure to count-leaves of the rest of the branches, or the cdr or the box-and-pointer structure. Note that the first recursive call will catch the second base case, while the second recursive call will catch the first base case, and eventually this reduces to the correct value for the number of leaves in this tree, as seen in the original box and pointer diagram, which had exactly one element in it. Slide 31.2.11 Now let's try a bit more complicated tree, as shown. Notice that this tree has the property that its first branch is just a leaf, but its second branch, defined as everything but the first branch, is itself a tree. Count-leaves thus applies to the box-and-pointer structure shown. In this case, the recursive call will add the number of leaves in the first branch, which is just the leaf, 5, since that is what the car returns, to the number of leaves in the tree, (7) since that is what the cdr of the original structure returns. Thus, the first recursive call will trigger the second base case, returning 1 for the single leaf there. The second recursive call will reduce to the case we saw on the last slide, recognizing this as another tree. Thus it unwinds the tree one more level, then returning 1 for the leaf in the first branch, and 0 for the empty tree in the second branch
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 31.2.12 countleaves- bigger example Now let's try a full-fledged tree, as shown here. In fact count-leaves will 国网 up with the correct value of 4, but let's see if we can quickly ce out why Slide 31.2.13 To do this. let's trace the calls to count-leaves. which countleaves- bigger example (define mytree (list 4 ( list 5 7)2) for convenience i have abbreviated as c-l Also notice that I have abbreviated the tree by its associated list structure, which I represent in blue to indicate that this represents a list, not a nmy-tree) procedure call ( (count (coumt leaves ((5 7)2))) Recursively, we know what this does. It applies count leaves to the first element of the tree. and to the rest of the tree and adds the result 9122003 countleaves-bigger example Slide 31.2.1 4 So here is that recursive decomposition. Note how we have define mytree (list mmryr-tree stripped out the two subtrees as shown (+(count leaves 4)(coumt leaves ((5 7)2)) Slide 31.2.15 Well. doingcount-leaves down the first sub-tree is countleaves- bigger example easy. By the second base case, this is just the value 1 (+(count leaves 4)(oout leaves ((5 7)2))
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 31.2.12 Now let's try a full-fledged tree, as shown here. In fact, count-leaves will recursively unwind the tree, ending up with the correct value of 4, but let's see if we can quickly trace out why. Slide 31.2.13 To do this, let's trace the calls to count-leaves, which for convenience I have abbreviated as c-l. Also notice that I have abbreviated the tree by its associated list structure, which I represent in blue to indicate that this represents a list, not a procedure call. Recursively, we know what this does. It applies countleaves to the first element of the tree, and to the rest of the tree, and adds the result. Slide 31.2.14 So here is that recursive decomposition. Note how we have stripped out the two subtrees, as shown. Slide 31.2.15 Well, doingcount-leaves down the first sub-tree is easy. By the second base case, this is just the value 1