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
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
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.
- 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.
- SICP exercise 1.11 (pp. 42). In this problem you implement a (fairly arbitrary?) recursive mathematical function using both recursive and iterative processes.
- SICP exercise 1.14 (pp. 44). In this problem you analyze execution of the
count-changeprocedure presented in the text.
- 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.pyanswers file (all Python results will go in here).
- Create a Python implementation of the SICP
count-changeprocedure (SICP Section 1.2.2).
- Create iterative and recursive Python implementations of the mathematical function in SICP exercise 1.11.
- When implementing an iterative process in Scheme, the Scheme interpreter uses tail-recursion. Explain what this means.
- Does Python support tail-recursion for iterative processes? Give a reference to where you find an answer to this.
- Re-implement in Python the
pi-sumprocedures 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?
- Back to Scheme! Let's continue with another iterative process implementation: do SICP exercise 1.16 (pp. 46).
- More iteration: SICP exercise 1.30 (pp. 60).
- Working towards higher-order procedures: Do SICP exercise 1.31 (a) (pp. 6061). Instead of 1.31 (b), simply describe whether your part (a) solution is iterative or recursive.
- SICP exercise 1.32 (a): Implement
accumulateand show how
productcan be defined with calls to
accumulate. Specify whether you have built the iterative or recursive version.
- SICP exercise 1.41 (pp. 77): Procedures that return procedures.
- SICP exercise 1.42 (pp. 77): More procedures that return procedures.
- 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
expntgenerates 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.