DOC PREVIEW
MIT 6 001 - Recursion and Iteration

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MIT 6 001 - Recursion and Iteration

Documents in this Course
Quiz 1

Quiz 1

6 pages

Databases

Databases

12 pages

rec20

rec20

2 pages

Quiz II

Quiz II

15 pages

Streams

Streams

5 pages

Load more
Download Recursion and Iteration
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recursion and Iteration and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recursion and Iteration 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?