# PS2

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 `ps2-ans.py`.

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`

### The Problems

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.

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 (fairly arbitrary?) recursive mathematical function using both recursive and iterative processes.
3. SICP exercise 1.14 (pp. 44). In this problem you analyze execution of the `count-change` procedure presented in the text.
4. 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.py` answers file (all Python results will go in here).
5. Create a Python implementation of the SICP `count-change` procedure (SICP Section 1.2.2).
6. Create iterative and recursive Python implementations of the mathematical function in SICP exercise 1.11.
7. When implementing an iterative process in Scheme, the Scheme interpreter uses tail-recursion. Explain what this means.
8. Does Python support tail-recursion for iterative processes? Give a reference to where you find an answer to this.
9. Re-implement in Python the `sum`, `inc`, `sum-cubes`, `identity`, `sum-integers`, and `pi-sum` procedures 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?
10. Back to Scheme! Let's continue with another iterative process implementation: do SICP exercise 1.16 (pp. 46).
11. More iteration: SICP exercise 1.30 (pp. 60).
12. Working towards higher-order procedures: Do SICP exercise 1.31 (a) (pp. 60–61). Instead of 1.31 (b), simply describe whether your part (a) solution is iterative or recursive.
13. SICP exercise 1.32 (a): 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.
14. SICP exercise 1.41 (pp. 77): Procedures that return procedures.
15. SICP exercise 1.42 (pp. 77): More procedures that return procedures.
16. 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).