# PS2

## 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

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).