Recent Changes - Search:

Home Assignments Lecture Blog Resources

91.301 Organization of Programming Languages
Prof. F. Martin

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.

Also we will begin using Python. In the exercises, you will be implementing the same process alternately in Scheme and Python.

What To Turn In

You will turn in two files for this assignment. One will hold all the Scheme code and evaluated results and will be in a file named ps2-ans.ss. The other will hold all the Python code and results and will be in a file named ps2-ans.py.

In both cases, put the problem number in a comment before the code for that problem. Scheme's comment character is a semi-colon and Python's is the hash-mark (aka pound symbol), #. In both languages, a comment may start anywhere on the line.

Submit your solutions electronically by logging into Mercury and typing

submit fredm 301-ps2 ps2-ans.ss ps2-ans.py

The Problems

Make sure you do the readings before or doing these! The reading associated with this problem set is listed on the Assignments page.

Note SICP = Structure and Interpretation of Computer Programs and CP = Core Python.

  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 (fairly arbitrary?) 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. OK ready to switch gears? Let's try this in Python. Type in and run the recursive-process version of factorial from CP Section 11.9.

    Now convert this to the iterative-process factorial (SICP section 1.2.1). Turn in this iterative implementation in your ps2-ans.py answers file (all Python results will go in here).
  5. Create a Python implementation of the SICP count-change procedure (SICP Section 1.2.2).
  6. Create iterative and recursive Python implementations of the mathematical function in SICP exercise 1.11.
  7. When implementing an iterative process in Scheme, the Scheme interpreter uses tail-recursion. Explain what this means.
  8. Does Python support tail-recursion for iterative processes? Give a reference to where you find an answer to this.
  9. Re-implement in Python the sum, inc, sum-cubes, identity, sum-integers, and pi-sum procedures from SICP Section 1.3.1. Show results of these procedures being run to demonstrate that they are working properly. Use the higher-order procedures implementation if it is possible. What decimal approximation do you get of pi?
  10. Back to Scheme! Let's continue with another iterative process implementation: do SICP exercise 1.16 (pp. 46).
  11. More iteration: SICP exercise 1.30 (pp. 60).
  12. Working towards higher-order procedures: Do SICP exercise 1.31 (a) (pp. 60–61). Instead of 1.31 (b), simply describe whether your part (a) solution is iterative or recursive.
  13. 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.
  14. SICP exercise 1.41 (pp. 77): Procedures that return procedures.
  15. SICP exercise 1.42 (pp. 77): More procedures that return procedures.
  16. 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

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