6.001 Recitation 3Structure and Interpretation of Computer Programs February 9, 2005Recursion and Iteration1. RecursionComponents:• “Wishful think ing”/recursive case/inductive step – Define the process in terms of itself• Base case – Specify non-decomposable part of the problemEverybody’s favorite recurs ive procedure( d e f i n e f a c t(lambda ( x )( i f (= x 0)1( ∗ x ( f a c t (− x 1 ) ) ) ) ) )2. Iteration (ie tail recursion)Process still defined in terms of itself, but nothing needs to be done with the results of thesmaller parts.Often achieved by passing an “accumulator” or state between calls.3. Recursive exercisesWhat do the following procedures mean?( d e f i n e mystery− func− 1(lambda ( x )(cond ((= x 0) #t )((= x 1) #f )( e l s e ( mystery− func− 1 (− x 2 ) ) ) ) ) )( d e f i n e mystery− func− 2(lambda ( x )( i f (= x 0)#f( not ( mystery− func− 2 (− x 1 ) ) ) ) ) )Write a recursive sum−nats that returns the sum of the n atur al numbers up to n.16.001 Structure and Interpretation of Computer Programs Recursion and IterationWrite a recursive fib.4. Iterative exercisesIs mystery−func−1 recursive or iterative? What about mystery−func−2? Why?Write an iterative sum−nats.Write an iterative fib .5. BrainteaserCan every recursive procedure be written
View Full Document