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

- 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. 60–61).
- 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. - 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`expnt`

generates a recursive process. Re-implement it as an iterative process (probably using a helper procedure).