Exercise 1.9

Question

Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.

(define (+ a b)
        (if (= a 0)
            b
            (inc (+ (dec a) b))
        )
)

(define (+ a b)
        (if (= a 0)
            b
            (+ (dec a) (inc b))
        )
)

Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?

Answer

Assume that:

(define (inc x) (+ x 1))
(define (dec x) (- x 1))

From the substitution principle we have for the first procedure:

(+ 4 5)
(inc (+ (dec 4) 5))
(inc ((inc (+ (dec 3) 5))))
(inc ((inc ((inc (+ (dec 2) 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

This procedure is recursive.

And for the second:

(+ 4 5)
(+ (dec 4) (inc 5))
(+ (dec 3) (inc 6))
(+ (dec 2) (inc 7))
(+ (dec 1) (inc 8))
(+ (dec 0) (inc 9))
9

The second one is iterative.

The easiest way to spot that the first process is recursive (without writing out the substitution) is to note that the "+" procedure calls itself at the end while nested in another expression; the second calls itself, but as the top expression.

source