Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
(+ 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 6)))
(inc (inc 7))
(inc 8)
9
The above process is recursive: we can tell by the shape of expansion followed by contraction in the substitution model, which indicates a chain of deferred operations that builds up before they can be performed. The memory used by this process in computing \(n + m\) grows linearly with \(n\).
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
(+ 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
The above process is iterative: it does not grow and shrink, and all of its state is contained in the two arguments to the + function. The number of steps required in computing \(n + m\) will grow linearly, but the amount of space used remains constant.