6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.3.3 Of course you already know that this won,t quite work, but let's3 Identify non-decomposable problems think about why. If we apply that version of fact to some argument, it will keep unwinding the application of factorial Must identify the " smallest"problems and solve directly into a multiplication and a smaller version of factorial. But Define 1!=1 before we can compute that multiplication, we have to get the value of the smaller version of factorial. and that will continue (define fact (lambda (n) to unwind to another version ad infinitum (if(=n1)1 The problem is that I didn't use my third step; I didn't consider *n(fact(-n1)))}) the smallest sized problem that I can solve directly, without using wishful thinking. In the case of factorial, that is just knowing that factorial of 1 is just 1. Once I find that smallest 471∞03 6001 sICP sized problem, I can control the unwinding of the computation by checking for that case and doing the direct computation when appropriate. In this way, I will terminate the recursive unwinding of the computation and accumulate all the deferred operations General form of recursive algorithms Slide 3.3. 4 test, base case, recursive case This in fact is a very common form, a common pattern for a recursive algorithm that has a test. a base case and a recursive (define fact case. The if controls the order of evaluation to decide whether (lambda (n) (f(= test for base case ve have the base case or the recursive case. the recursive case 1 base case controls the unwinding of the computation, doing so until we (-n 1)) i recursive case reach the base case ))) base case: smallest (non-decomposable) problem recursive case: larger(decomposable) problem 4:a03 6 001 SICP Slide 3.3.5 Summary of recursive processes To summarize. we have now seen how to design recursive algorithms, by using this idea of wishful thinking to separate the problem into a simpler version of the same problem, do that decomposition and identify the smallest version of the problem 3. identify non-decomposable(smallest)problems that will stop the unwinding of the computation into simpler Recursive algorithms have versions of the same problem. As a consequence, algorithms associated with this kind of approach have a test, a base case 2. recursive case and a recursive case to control the order of evaluation in order to unwind the computation into simpler versions of the same 6001S 6.001 Notes: Section 3. 46.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.3.3 Of course you already know that this won't quite work, but let's think about why. If we apply that version of fact to some argument, it will keep unwinding the application of factorial into a multiplication and a smaller version of factorial. But before we can compute that multiplication, we have to get the value of the smaller version of factorial, and that will continue to unwind to another version, ad infinitum. The problem is that I didn't use my third step; I didn't consider the smallest sized problem that I can solve directly, without using wishful thinking. In the case of factorial, that is just knowing that factorial of 1 is just 1. Once I find that smallest sized problem, I can control the unwinding of the computation, by checking for that case and doing the direct computation when appropriate. In this way, I will terminate the recursive unwinding of the computation and accumulate all the deferred operations. Slide 3.3.4 This in fact is a very common form, a common pattern for a recursive algorithm that has a test, a base case and a recursive case. The if controls the order of evaluation to decide whether we have the base case or the recursive case. The recursive case controls the unwinding of the computation, doing so until we reach the base case. Slide 3.3.5 To summarize, we have now seen how to design recursive algorithms, by using this idea of wishful thinking to separate the problem into a simpler version of the same problem, do that decomposition and identify the smallest version of the problem that will stop the unwinding of the computation into simpler versions of the same problem. As a consequence, algorithms associated with this kind of approach have a test, a base case, and a recursive case to control the order of evaluation in order to unwind the computation into simpler versions of the same problem. 6.001 Notes: Section 3.4