Exercise 1.09

This is the First question in Section to of Chapter one in Sicp. Here we are comparing recursion and iteration.

The Question

**Exercise 1.09:**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?

My Thoughts

Before we start with this question, let us recap what is recursion and what is iteration. (In simple language. I do not consider my words fit to be a definition)

What is Recursion?

A process is a Recursive Process only if the “shape” of the process changes, and the data of the various steps involved is maintained by the interpreter internally.

What is Iteration?

A process is an iterative process only if the shape does not change and the data of the various steps involved is maintained by a function in the form of various parameters

The Answer

Let us manually evaluate (+ 4 5) where the process + is the first definition. So:

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

We can see that the “shape” of the process changes. We also observe that the number of levels inc was executed is only known by the interpreter. Thus, we can say that is a recursive process

Now let us evaluate (4 5) where + is the second definition:

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

We see that the “shape” of the process remains the same. We should also note that the information where the Interpreter is maintained by the function. We can hence, conclude that that this is an iterative process.