6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology clause of the cond and repeat the process. This continues for however many clauses are contained in the cond until either a true predicate is reached or we reach a clause with the special keyword e lse. In this latter case, that predicate is treated as true, and the subsequent expressions are evaluated Given that form for cond, we can see how our fibonacci procedure captures the idea we expressed. We keep recursively solving smaller sized problems until we get to a base case. Notice that here we have two base cases. not one Also notice that while this is a recursive procedure, it is different from our earlier ones. Here, there are two recursive calls to the procedure in the body, rather than just one. Our question is whether this leads to a different kind of behavior, or a different order of growth Slide 4.2.3 A tree recursion This does give rise to a different kind of behavior, which we can easily see with the illustrated diagram. To solve a problem of size 4, notice that we have to solve two problems, one of size 3 and one of size 2, and each of these requires solving two smaller problems, and so on This gives rise to a kind of tree of things we have to do, and Fib 1 Fib each recursive call gives rise to two subproblems of smaller size. This leads to a different order of growth Fib1 Fib o 6001 sICP Orders of growth for Fibonacci Slide 4.2.4 Let ta be the number of steps that we need to take to solve the case o measure the order of growth, let,'s let t of n denote the for size n. Then number of time steps we need to solve a problem of size n t=tnt+t,2=25,2=454=8 From our tree. we see that to do this we need to solve In space, we have one defered operation for cach increment of the problem of size n-1, and a problem of size n-2.We could stack of -e(n)-linear actually work out a detailed analysis of this relationship, but for our purposes, we can approximate this as roughly the same as solving two problems of size n-2. Expanding a step further, this is roughly the same as solving 4 problems of size n-4 and roughly the same as solving 8 problems of size n-6. A little I math shows that in general this reduces to 2 to the power of n/2 This is an example of an exponential order of growth, and this is very different from what we saw earlier. To convince yourself of this, assume that each step takes one second and see how much time it would take for an exponential process as compared to a linear one, as n gets large In terms of space, our tree shows us that we have basically one deferred operation for step, or in other words, the maximum depth of that tree is linear in the size of the problem, and the maximum depth exactly captures the maximum number of deferred operations 6.001 Notes: Section 4.36.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. clause of the cond and repeat the process. This continues for however many clauses are contained in the cond until either a true predicate is reached, or we reach a clause with the special keyword else. In this latter case, that predicate is treated as true, and the subsequent expressions are evaluated. Given that form for cond, we can see how our fibonacci procedure captures the idea we expressed. We keep recursively solving smaller sized problems until we get to a base case. Notice that here we have two base cases, not one. Also notice that while this is a recursive procedure, it is different from our earlier ones. Here, there are two recursive calls to the procedure in the body, rather than just one. Our question is whether this leads to a different kind of behavior, or a different order of growth. Slide 4.2.3 This does give rise to a different kind of behavior, which we can easily see with the illustrated diagram. To solve a problem of size 4, notice that we have to solve two problems, one of size 3 and one of size 2, and each of these requires solving two smaller problems, and so on. This gives rise to a kind of tree of things we have to do, and each recursive call gives rise to two subproblems of smaller size. This leads to a different order of growth. Slide 4.2.4 To measure the order of growth, let's let t of n denote the number of time steps we need to solve a problem of size n. From our tree, we see that to do this, we need to solve a problem of size n-1, and a problem of size n-2. We could actually work out a detailed analysis of this relationship, but for our purposes, we can approximate this as roughly the same as solving two problems of size n-2. Expanding a step further, this is roughly the same as solving 4 problems of size n-4 and roughly the same as solving 8 problems of size n-6. A little math shows that in general this reduces to 2 to the power of n/2 steps. This is an example of an exponential order of growth, and this is very different from what we saw earlier. To convince yourself of this, assume that each step takes one second, and see how much time it would take for an exponential process as compared to a linear one, as n gets large. In terms of space, our tree shows us that we have basically one deferred operation for step, or in other words, the maximum depth of that tree is linear in the size of the problem, and the maximum depth exactly captures the maximum number of deferred operations. 6.001 Notes: Section 4.3