• View
• Edit
• History
• Print

PS2

Home Assignments Lecture Blog Resources Project Discussion Group

91.301 Organization of Programming Languages
Prof. F. Martin

Out: Feb 2, 2009
Due: Feb 6, 2009

Problem Set 2: Iterative vs. Recursive Processes and Higher-Order Procedures

We will delve into the difference between iterative and recursive processes. A recursive procedure may actually invoke an iterative or recursive process! (Warning -- by the time you are done with this problem set, you will be sick of this topic. Sorry about that)

Also we will study higher-order procedures. This is the idea of passing procedures as inputs to other procedures, and procedures that construct and output new procedures.

What To Turn In

In a file named ps2-ans.ss, turn in the file that holds all the Scheme code and evaluated results.

Put the problem number in a comment before the code for that problem. Scheme's comment character is a semi-colon; a comment may start anywhere on the line.

Submit your solutions electronically by logging into Mercury and typing

Reading

Read SICP, Section 1.2 and Section 1.3. You may skip 1.2.6, unless you are really enjoying the mathematics and number theory.

The Problems

Make sure you do the readings before or doing these!

1. SICP exercise 1.9 (pp. 36). In this problem, you will study two implementations of addition in terms of increment and decrement, and analyze whether the implementations are iterative or recursive.
2. SICP exercise 1.11 (pp. 42). In this problem, you implement a recursive mathematical function using both recursive and iterative processes.
3. SICP exercise 1.14 (pp. 44). In this problem, you analyze execution of the count-change procedure presented in the text.
4. When implementing an iterative process in Scheme, the Scheme interpreter uses tail-recursion. Explain what this means.
5. SICP exercise 1.16 (pp. 46).
6. More iteration: SICP exercise 1.30 (pp. 60).
7. Working towards higher-order procedures: Do SICP exercise 1.31 (a) and (b) (pp. 60–61).
8. SICP exercise 1.32 (a): Implement accumulate and show how sum and product can be defined with calls to accumulate. Specify whether you have built the iterative or recursive version.
9. SICP exercise 1.41 (pp. 77): Procedures that return procedures.
10. SICP exercise 1.42 (pp. 77): More procedures that return procedures.
11. Here is an implementation of expnt, a procedure that generates a procedure for raising its input to its argument. E.g., (expnt 2) generates a procedure for squaring a number. The provided implementation of expnt generates a recursive process. Re-implement it as an iterative process (probably using a helper procedure).

Honors, Graduate Students, and Undergrads Looking for More

12. SICP exercise 1.43 (pp. 77): Repeated application of procedures.