6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.4.4 Intuition for iterative factorial So thats our goal, to compute factorial in a different way that not characterized by those deferred multiplications 7103 6 001 SICP Slide 3. 4.5 Intuition for iterative factorial and here is the intuition behind this different approach. Let's. same as you would do if calculating 4l by hand think about how you might do this if you were executing the 1. multiply 4 by 3 first two numbers, and keep track of that temporary produ o computation by hand. One way to do this is to multiply out 2. multiply 12 by 2 gives 24 3. multiply 24 by 1 plus the next stage in the computation. For example, for factorial of 4, you would multiply out 4 by 3, keep track of the result, 12, and the fact that the next thing to multiply is 2. You would then multiply the current result, 12, by 2, keeping track of that result and the next thing to multiply by < s1403 Intuition for iterative factoria Slide 3. 4.6 same as you would do if calculating 4 by hand Notice that in this version, we only need to keep track of 2 1. multiply 4 by 3 gives 12 things, the current product, and the next thing to do. This is 2. multiply 12 by 2 different from the recursive case, where we were blindly multiply 24 by gives 24 .At each step, only need to remember keeping track of each pending multiplication. Here, we replac the previous product by the new one, and the next multiplier by the new one, whereas in the previous case we had to keep track of each deferred operation, i.e. I have to multiply by 2, then I have to multiply by 3, then Slide 3. 4.7 Intuition for iterative factorial hus, we only need a constant amount of space. To stress, think same as you would do if calculating 4! by hand about the recursive case. There. we had to write down that i 1. multiply 4 by 3 gives 12 have a pending operation of multiplication by some number, 2. multiply 12 by 2 plus another pending operation of multiplication by another 3. multiply 24 by 1 gives 24 number, and so on. Keeping track of each such pending . At each step, only need to remember previous product, next multiplier operation takes a bit more space. In this case, I only need two pieces of information, the current product and the next multiplier6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.4.4 So that's our goal, to compute factorial in a different way that is not characterized by those deferred multiplications Slide 3.4.5 ... and here is the intuition behind this different approach. Let's think about how you might do this if you were executing the computation by hand. One way to do this is to multiply out the first two numbers, and keep track of that temporary product, plus the next stage in the computation. For example, for factorial of 4, you would multiply out 4 by 3, keep track of the result, 12, and the fact that the next thing to multiply is 2. You would then multiply the current result, 12, by 2, keeping track of that result and the next thing to multiply by. Slide 3.4.6 Notice that in this version, we only need to keep track of 2 things, the current product, and the next thing to do. This is different from the recursive case, where we were blindly keeping track of each pending multiplication. Here, we replace the previous product by the new one, and the next multiplier by the new one, whereas in the previous case we had to keep track of each deferred operation, i.e. I have to multiply by 2, then I have to multiply by 3, then ... Slide 3.4.7 Thus, we only need a constant amount of space. To stress, think about the recursive case. There, we had to write down that I have a pending operation of multiplication by some number, plus another pending operation of multiplication by another number, and so on. Keeping track of each such pending operation takes a bit more space. In this case, I only need two pieces of information, the current product and the next multiplier