# PS2

Home Assignments Lecture Blog Resources Project Discussion Group

**91.301 Organization of Programming Languages** **Prof. F. Martin**

Out: Jan 31, 2011

Due: Feb 4, 2011

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

### What To Turn In

In a file named `ps2-ans.rkt`

, turn in the file that holds all the Scheme code and evaluated results.

Put the problem number in a comment before the code for that problem. Scheme's comment character is a semi-colon; a comment may start anywhere on the line.

Submit your solutions electronically by logging into the `cs.uml.edu`

cluster and typing

`submit fredm 301-ps2 ps2-ans.rkt`

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