乐正

Actions speak louder than words.

Sicp-ex1-9

问题

下面几个过程定义了一种加起来两个正整数的方法,它们都基于过程inc(它将参数增加1) 和dec(它将参数减少1).

1
2
3
4
5
6
7
8
9
(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b)))

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

请用代换模型展示这两个过程在求值(+ 4 5)时所产生的计算过程。这些计算过程是递归 的或者迭代的吗?

解答

第一个计算过程的代换模型如下:

1
2
3
4
5
6
7
8
9
10
(+ 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

这一过程构造起一个推迟执行的操作所形成的链条,收缩阶段表现为这些运算实际的执行, 是递归计算过程。

第二个计算过程代换模型:

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

该计算过程其状态可以用固定数目的状态变量$a$, $b$描述,是迭代计算过程。

draft

« sicp-ex1-8 sicp-ex-1-10 »

Comments