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
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.
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.
- 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 recursive mathematical function using both recursive and iterative processes.
- When implementing an iterative process in Scheme, the Scheme interpreter uses tail-recursion. Explain what this means.
- 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) and (b) (pp. 6061).
- SICP exercise 1.32 (a only): 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).