# SICP Exercise 1.9 – Process Illustration

## Prompt

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 (inc x) (+ x 1))
(define (dec x) (- x 1))

; Implementation 1
(define (plus-v1 a b)
(if (= a 0)
b
(inc (plus-v1 (dec a) b))))

; Implementation 2
(define (plus-v2 a b)
(if (= a 0)
b
(plus-v2 (dec a) (inc b))))
``````

Using the substitution model, illustrate the process generated by each procedure in evaluating `(plus-v1 4 5)` and `(plus-v2 4 5)`. Are these processes iterative or recursive?

## Solution

An important distinction to reiterate here is the difference between a recursive procedure and a recursive process. A procedure that references itself is a recursive procedure. In the implementations of `plus` above, both procedures are recursive. It’s a static construct. But a recursive procedure, at runtime, can generate an iterative process! Whether a process is iterative or recursive depends on the manner in which the computation is carried out.

A common way to illustrate each evaluation step of a procedure application process is using the substitution model to show the expression that gets evaluated.

Here’s an example of using substitution applied to the first plus procedure.

``````(plus-v1 3 5)
(inc (plus-v1 2 5))
(inc (inc (plus-v1 1 5)))
(inc (inc (inc (plus-v1 0 5))))
(inc (inc (inc 5)))
(inc (inc (+ 5 1)))
(inc (inc 6))
(inc (+ 6 1))
(inc 7)
(+ 7 1)
8``````

The first `(plus-v1 3 5)` expression is our initial procedure invocation.

If we evaluate this we will get our next result. Since 3 does not equal 0, the `if` statement is skipped and we get `(inc (plus-v1 2 5))`. If we evaluate this again, notice that we don’t expand the expression for `inc` yet because we don’t know what the value of it’s argument is. We need to continue expanding the plus expressions until we reach an actual primitive value.

In other words, we are deferring the evaluation of `inc` until later. If you look at our full expansion, we only start calling `inc` when we get the value `5` back from `(plus-v1 0 5)`. This chain of deferred operations during the evaluation process makes this a recursive process!

Now contrast this to the other plus procedure plus-v2.

``````(plus-v2 3 5)
(plus-v2 2 6)
(plus-v2 1 7)
(plus-v2 0 8)
8``````

In each step of the evaluation, no operation is deferred. We’re incrementing one number, decrementing the other and calling the function again. There are no function calls waiting for a result. This is an iterative process. In iterative processes, the complete state is computed in each step. In other words, prior to calling the procedure, all the parameters that would bind to the arguments are provided with primitive values.