excercise-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)

1
2
3
4

(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 theseprocesses iterative or recursive?

Ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

(+ 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

; Method 2
(+ 4 5) ->
(+ 3 6) ->
(+ 2 7) ->
(+ 1 8) ->
(+ 0 9) ->
9

从整个式子的运算过程来看,方式一是线性递归过程,方式二为线性迭代过程.