1.9.md

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)))) ; <-- Create chain (recursive)

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b)))) ; <-- Pass state (iterative)

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

Answer

Despite sharing a recursive implementation, the first process evolves recursively and the second process evolves iteratively.

This distinction arises from operation order: the recursive process calls itself as an argument to inc, while the iterative process passes calls to inc and dec as arguments to itself. The former produces a chain of distributed computation (recursion) while the latter maintains its state in the result of (dec a) and (inc b) (iteration).