6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.2.10 The fact procedure is a recursive algorithm That means that fact gives rise to what we call a recursive process. In the substitution model we can see that this is In the substitution mode, the expression keeps growing characterized by a set of deferred operations, in which the multiplication is deferred while we go off to get the sub- ★3(fact2)) (*3(*2(fact1))) computation of the simpler version of fact. Once we get to a Other ways to identify will be described next time simple case, we can start accumulating those stacked up operations. We will come back to this idea next time 7103 6 001 SICP 10n0 6.001 Notes: Section 3.3 Slide 3.3.1 How to design recursive algorithms Now that we have seen our first more interesting procedure, follow the general pattern fact, let's step back and generalize the ideas we used to capture this computation in a procedure 2. decompose the problem What are the general steps that we use in creating a recursive 3. identify non-decomposable(smallest)problems procedure like this? We have three stages: as shown her 1. wishful thin kin The first stage is called wishful thinking. The idea is as Assume the desired procedure exists follows. If I want to create a solution to some problem, I first assume that I have available a procedure that will solve the want to implement fact? oK, assume it exists BUT, only solves a smaller version of the proble oblem, but only for versions of the problem smaller than the current one. In the case of factorial, I assume(wishfully) that I 71003 can solve factorial for problems of size smaller than n se the problem Slide 3.3.2 Solve a problem by Given that assumption, the second stage proceeds to design 1. sole a smaller instance sing wishful thinking) solution to the problem. In particular, I can use the existence of 2. convert that solution to the desired solution a solution to the smaller sized problem, plus a set of simple operations, to design the solution to the larger sized problem Must design the strategy before coding We this with factorial where mbined the solution to n=nn1)n2=n(n1)(n2)]=n*(n-1) a smaller version of factorial, plus a multiplication, to create the solve the smaller instance, multiply it by n to get solution solution to the full version of factorial (define fact Notice that the second step here requires some ingenuit (Lambda (n)(*n (fact (-n 1)))) should be careful to think through this strategy, betony.One I beginning to code up a solution. In the case of factorial, we saw how we did this decomposition into a multiplication and a maller version of factorial With this, we can build a first version of the procedure as shown at the bottom of the slide6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.2.10 That means that fact gives rise to what we call a recursive process. In the substitution model we can see that this is characterized by a set of deferred operations, in which the multiplication is deferred while we go off to get the sub￾computation of the simpler version of fact. Once we get to a simple case, we can start accumulating those stacked up operations. We will come back to this idea next time. 6.001 Notes: Section 3.3 Slide 3.3.1 Now that we have seen our first more interesting procedure, fact, let's step back and generalize the ideas we used to capture this computation in a procedure. What are the general steps that we use in creating a recursive procedure like this? We have three stages: as shown here. The first stage is called wishful thinking. The idea is as follows. If I want to create a solution to some problem, I first assume that I have available a procedure that will solve the problem, but only for versions of the problem smaller than the current one. In the case of factorial, I assume (wishfully) that I can solve factorial for problems of size smaller than n. Slide 3.3.2 Given that assumption, the second stage proceeds to design a solution to the problem. In particular, I can use the existence of a solution to the smaller sized problem, plus a set of simple operations, to design the solution to the larger sized problem. We saw this with factorial, where we combined the solution to a smaller version of factorial, plus a multiplication, to create the solution to the full version of factorial. Notice that the second step here requires some ingenuity. One should be careful to think through this strategy, before beginning to code up a solution. In the case of factorial, we saw how we did this decomposition into a multiplication and a smaller version of factorial. With this, we can build a first version of the procedure as shown at the bottom of the slide