Exercise 1.9

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?

Both of these procedures work by gradually decrementing a to \(0\), and then incrementing either the result or b each time. The variation is in whether this is done recursively or iteratively.

Looking through the first implementation, we see in the else clause the outermost call is to inc. Thus, inc is being deferred till the inner call to + is evaluated. Therefore, this implementation is recursive. We can prove this using the substitution model and with the help of racket's racket/trace module:

#lang sicp
(#%require racket/trace)

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

(trace +)

(+ 5 10)

>{+ 5 10}
> {+ 4 10}
> >{+ 3 10}
> > {+ 2 10}
> > >{+ 1 10}
> > > {+ 0 10}
< < < 10
< < <11
< < 12
< <13
< 14
<15
15

Similarly, the second implementation calls itself in the outermost expression of the else-clause i.e. a tail call. Therefore this is an iterative process:

#lang sicp
(#%require racket/trace)

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

(trace +)

(+ 5 10)

>{+ 5 10}
>{+ 4 11}
>{+ 3 12}
>{+ 2 13}
>{+ 1 14}
>{+ 0 15}
<15
15