**Exercise 3.9**

Let’s start with the recursive *factorial*:

```
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
```

For simplicity, especially since drawing these pictures in OpenOffice is a bit tedious, let’s trace out the evaluation of *(factorial 3)* instead of *(factorial 6)*. When the procedure *factorial* is applied to the argument *3* a new environment *E1* is created who’s parent environment is the environment in which *factorial* was defined (the global environment), and in which the formal parameter *n* is bound to the value *3*. Then the body of *factorial* is evaluated in this new environment, resulting in another application of *factorial* with *2* as an argument. This creates a new environment *E2* in which the formal parameter *n* is bound to *2*. The environment *E3* is created in a similar manner, with *n* bound to *1*. Finally the base case of *factorial* is reached, the computation unwinds and finishes:

Now let’s examine the iterative version of *factorial*:

```
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
```

Again everything starts with the application *(factorial 3)*. The body of *factorial* is evaluated in an environment *E1*, where the formal parameter *n* is bound to *3*. This results in the application *(fact-iter 1 1 n)*, which reduces to evaluating the body of the procedure *fact-iter* in a new environment *E2* with the formal parameters *product*, *counter*, and *max-count* bound to *1*, *1*, and *3* respectively. The process continues with the environments *E3*, *E4*, and *E5* being created along the way until the computation finally ends:

## Leave a Reply