6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.4.1 So we have introduced recursive procedures, and we have nowIterative algorithms een an example of building a recursive procedure to implement factorial. Now, let's look at a different kind of procedure, an iterative procedure for computing factorial. In doing this, we are going to see how we can develop procedures with different evolutions that compute the same basic computation 471∞03 6001 sICP Slide 3.4.2 In a recursive algorithm, bigger operands => more space To set the stage for this, here is our factorial procedure from last time. Remember that this was a nice little procedure that *n(fact(-n1)))))) first checked to see if we were in the base case. and if we were (*4(Eact3)) 3 (fact 2) eturned the answer 1. If we were not, the procedure reduced (*4(*3(*21)0 the problem to multiplying n by a recursive call to factorial of n-1. One of the properties of this procedure was that it held set of deferred operations. To compute factorial of n, it had to hold onto a multiplication while it went off to compute the subproblem of a simpler version of factorial, and that in turn 601 SICP I required another deferred operation. Thus, the procedure had to keep track of something to do, once it was done computing a subproblem, and this meant that as the argument to the procedure gets larger, we would have more things to keep track of. We would like to see if there is another way of computing factorial, without all of those deferred operations Slide 3.4.3 rative algorithms The specific question we want to consider is whether we can In a recursive algorithm, bigger ope design an algorithm for factorial that uses only constant space efine fact (lambda (n By this we mean that the computation does not require keeping *nact(-n1)))))) fact 4) track of any deferred operations, but rather can perform its work without using up any additional memory to keep track of (*4(3 things to do An iterative algorithm uses constant space6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.4.1 So we have introduced recursive procedures, and we have now seen an example of building a recursive procedure to implement factorial. Now, let's look at a different kind of procedure, an iterative procedure for computing factorial. In doing this, we are going to see how we can develop procedures with different evolutions that compute the same basic computation. Slide 3.4.2 To set the stage for this, here is our factorial procedure from last time. Remember that this was a nice little procedure that first checked to see if we were in the base case, and if we were, returned the answer 1. If we were not, the procedure reduced the problem to multiplying n by a recursive call to factorial of n-1. One of the properties of this procedure was that it held a set of deferred operations. To compute factorial of n, it had to hold onto a multiplication while it went off to compute the subproblem of a simpler version of factorial, and that in turn required another deferred operation. Thus, the procedure had to keep track of something to do, once it was done computing a subproblem, and this meant that as the argument to the procedure gets larger, we would have more things to keep track of. We would like to see if there is another way of computing factorial, without all of those deferred operations. Slide 3.4.3 The specific question we want to consider is whether we can design an algorithm for factorial that uses only constant space. By this we mean that the computation does not require keeping track of any deferred operations, but rather can perform its work without using up any additional memory to keep track of things to do