1.9 Exercise 1.9

The evaluation of the expression (+ 4 5) with the first procedure using the substition model is as follows:

(+ 4 5)

(inc (+ (dec 4) 5))

(inc (+ 3 5))

(inc (inc (+ (dec 3) 5)))

(inc (inc (+ 2 5)))

(inc (inc (inc (+ (dec 2) 5))))

(inc (inc (inc (+ 1 5))))

(inc (inc (inc (inc (+ (dec 1) 5)))))

(inc (inc (inc (inc (+ 0 5)))))

(inc (inc (inc (inc 5))))

(inc (inc (inc 5)))

(inc (inc 7))

(inc 8)

9

The first procedure generates a recursive process.

The evaluation using the second procedure generates an iterative process:

(+ 4 5)

(+ (dec 4) (inc 5))

(+ 3 6)

(+ (dec 3) (inc 6))

(+ 2 7)

(+ (dec 2) (inc 7))

(+ 1 8)

(+ (dec 1) (inc 8))

(+ 0 9)

9