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.

Comments

When we did this exercise with David Beazley in his SICP course, he joked that this exercise was sort of like desert island coding. You’re stranded on a desert island… if you only had increment and decrement, how would you add addition and multiplication? Funny enough, he was actually stuck in a scenario not too far from that when he had to re-invent the shell using python while locked in a secure vault (very entertaining talk!).

What I like about this exercise is how effectively it gives students a feel for the difference between recursive and iterative processes. By expanding out an expression by hand using substitution, you can see operations expanding and contracting. This raises a lot of interesting ideas and questions around performance, recursive function base-cases, and whether all recursive forms have an iterative form and vice-versa.