Recent Changes - Search:
OPLspr14 /

PS2

Home Assignments Lecture Blog Resources Project Discussion Group

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!

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

Please use the autograder to obtain starter code, and upload your completed work there. Here is a direct link to the assignment: https://grader.cs.uml.edu/assignments/356

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 doing these!

Please note, if you are working from a printout, go to the course web site to find links to the exercises in the online version of the text, and the code for exercise 10.

  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. When implementing an iterative process in Scheme, the Scheme interpreter uses tail-recursion. Explain what this means.
  4. SICP exercise 1.16 (pp. 46).
  5. More iteration: SICP exercise 1.30 (pp. 60).
  6. Working towards higher-order procedures: Do SICP exercise 1.31 (a) and (b) (pp. 60–61).
  7. SICP exercise 1.32 (a only): 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.
  8. SICP exercise 1.41 (pp. 77): Procedures that return procedures.
  9. SICP exercise 1.42 (pp. 77): More procedures that return procedures.
  10. 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

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