Exercise 3.9.  In section 1.2.1 we used the substitution model to 
analyze two procedures for computing factorials, a recursive version

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

and an iterative version

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

Show the environment structures created by evaluating (factorial 6) 
using each version of the factorial procedure.

————————————————————————————————————————————————————————————————————————

recursive version:

First we create an environment for the factorial call.

│ n : 6
└───────
 (if (= n 1)
     1
     (* n (factorial (-n 1))))

We evaluate (* n (factorial (-n 1))) by looking up n, which we have as 
6, and *, -, and factorial, which are bound in the global environment.

The * and - calls create two more environments where n is 6, and the new 
call to factorial creates a frame with n bound to 5.

Environment structures for *, -, and factorial will be created for each 
integer from 6 to 2.  Finally the 1 will be returned and the 
multiplications will propagate back out through the frames that still 
contain the earlier values of n.


iterative version:

Again the interpreter creates an environment with n bound to 6 and 
evaluates the body of the factorial function in it.  This looks up 
fact-iter and creates a new environment for that call:

│ product : 1
│ counter : 1
│ max-count : 6
└───────────────
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count))

First (> counter max-count) is evaluated, and then the nested 
fact-iter call is evaluated, first by evaluating (* counter product) 
and (+ counter 1) and then by calling fact-iter.

The fact-iter call creates a new environment:

│ product : 1
│ counter : 2
│ max-count : 6
└───────────────

Since this is a tail call, the original frame created by the first 
call to fact-iter could be replaced by this new one.  That is why 
this version runs in constant memory and the other version does not.

New frames are created with increasing values of product and counter 
until the max-count is reached.  Unlike the recursive version, when 
the final call to fact-iter is evaluated, the answer is already known, 
there is no stack of frames with pending multiplication operations 
waiting to be performed.