练习1.9

第一个过程：

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

为了与解释器内置的+混淆 这里将过程命名为plus

求值过程：

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

可以明显看到 随着计算过程的进行 代码先伸展后收缩 每一个inc都被推迟到直到完全展开后再进行计算

这是一个递归过程

在展开阶段里，这一计算过程构造起一个推迟进行的操作所形成的链条，收缩阶段表现为这些运算的实际执行。这种类型的计算过程由一个推迟执行的运算链条刻画，称为一个递归计算过程。要执行这种计算过程，解释器就需要维护好那 些以后将要执行的操作的轨迹。在计算阶乘n!时，推迟执行的乘法链条的长度也就是为保存其轨迹需要保存的信息量，这个长度随着n值而线性增长（正比于n)就像计算中的步骤数目一样。这样的计算过程称为一个线性递归过程。

引自SICP第22页

第二个过程：

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

求值过程：

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

由于Lisp的解释器总是尾递归优化的 这个计算过程代码没有明显伸展 它通过不断更新a和b的值迭代地完成计算过程

这是一个迭代过程

一般来说，迭代计算过程就是那种其状态可以用固定数目的状态变量描述的计算过程;而与此同时，又存在着一套固定的规则，描述了计算过程在从一个状态到下一状态转换时，这些变量的更新方式；还有一个（可能有的）结束检测，它描述这一计算过程应该终止的条件。在计算n!时，所需的计算步骤随着n线性增长，这种过程称为线性迭代过程。

我们还可以从另一个角度来看这两个过程之间的对比。在迭代的情况里，在计算过程中的任何一点，那几个程序变量都提供了有关计算状态的一个完整描述。如果我们令上述计算在某两个步骤之间停下来，要想重新唤醒这一计算，只需要为解释器提供有关这三个变量的值。而对千递归计算过程而言，这里还存在着另外的一些“隐含”信息，它们并未保存在程序变量里，而是由解释器维持着，指明了在所推迟的运算所形成的链条里的漫游中，“这一计算过程处在何处”。这个链条越长，需要保存的信息也就越多。

引自SICP第23页

trace追踪过程可见SICP解题集 练习1.9