SICP 笔记：1.2 – 1.2.6

计算机程序的构造和解释 是这样的一本书：它将大量编程中的基本技巧，用一本正经的语言讲出来，帮助你在构建大型软件时使用这些技巧来控制代码中的复杂性。而这些技巧的共性之一就是，将复杂的事物，通过隐藏细节的方式进行组合和抽象。我认为如果一个合格的程序员只需要读三本书的话，这本书便位列其中。

写笔记是为了自己在读书的过程中能够更好地思考和理解，这份笔记的定位是排除书中的例子，将书中的结论和观点用自己的话重新描述一遍，以简体中文版为主，因为似乎翻译的质量不高，所以也会参考英文原版。本书的英文原版以 CC-BY-SA 发行，相信公开发布这份笔记没有版权方面的问题。其实这份笔记对没有读过本书的人没有什么意义，因为本书的重要价值在于书中的例子，而这份笔记不会涉及这些例子，所以请纯当我在自言自语。

1.2 过程与它们产生的计算

在程序设计中，能够对计算过程中各种动作的进行情况进行规划是十分重要的，只有看清楚各种不同种类的过程会产生怎样的计算过程，才能更好地反向构造出可靠的程序，使之能表现出所需的行为。

1.2.1 线性的递归和迭代

计算阶乘可能有多种方式，其中一种基于这样的认识「对于一个正整数 n, 它的阶乘就等于 n * (n - 1)!」。另一种方法则可以将阶乘描述为「维持一个用来表示乘积的 product, 然后从 1 开始递增计数器 counter, 并将 product 设置为 product * counter, 直到 counter 大于 n, product 就是 n 的阶乘」。

从结果来看，这两种计算方法并没有什么差异，但如果我们考虑这两种方式的「形状」，即计算过程中时间和空间等资源的消耗情况，就会发现他们有很大区别。

第一个计算过程，如果使用前文提到的代换模型进行展开，会呈现出一种先逐步展开，而后收缩的形状。在展开阶段，这一计算过程构造器了一个「推迟执行的操作」所形成的链条，具体就是乘法运算，收缩阶段表现为这些运算的实际执行。这种类型的计算过程被称为「递归计算过程」，在执行时，解释器必须维护好那些以后要执行的操作的轨迹，在计算 n! 时，推迟执行的乘法链条的长度随 n 呈线性增长，这样的计算过程被称为「线性递归过程」。

与之对应的，第二个计算过程里并没有任何增长或收缩。对于任何一个 n, 在计算过程中的每一步，解释器需要保存的状态只有变量 product, counter 和 n 的当前值。我们称这种过程为「迭代计算过程」。一般来说，迭代计算过程就是那种其状态可以用固定数目的「状态变量」描述的计算过程；而与此同时，又存在着一套固定的规则，描述了计算过程在从一个状态转换到下一个状态时，这些变量的更新方式；以及一个通常都会有的结束检测，它描述了这一计算过程应该终止的条件。在计算 n! 时，所需的计算步骤随 n 线性增长，这种过程被称为「线性迭代过程」。

我们还可以换一个角度来对比这两个过程。在迭代的例子中，在计算过程中的任何一点，有关计算状态的完整描述都被包含在了那三个状态变量中。如果我们令上述计算过程在某两个步骤中停下来，在重新恢复这个计算过程时，只需要为编译器提供这三个变量的值。

而对于递归的计算过程而言，存在着一些「隐藏」的信息，它们并未保存在变量中，而是由解释器维持着，以指明在所推迟的运算所形成的链条中，当前计算过程所处的状态。这个链条越长，需要保存的信息就越多。

在后文中我们将会讨论过程在计算机上的实现，那时将会看到，所有的迭代过程都可以「以硬件的方式」实现为一个机器，其中只需要固定数目的寄存器，无需任何辅助存储器。而要实现递归计算过程，就需要一种机器，其中使用到了一种被称为「堆栈」的辅助数据存储结构。

在对比「迭代过程」和「递归过程」时，我们必须当心，不要混淆了「递归计算过程」和「递归过程」的概念。当我们说一个过程是递归的时候，描述的是一个代码的语法形式上的事实，说明这个过程的定义中直接或简介地引用了该过程本身。

而当我们说某一计算过程具有某种例如线性递归的模式时，我们说的是这一计算过程所产生的计算方式，而不是代码书写上的形式。当我们说某个递归过程将产生一个迭代的计算过程时，可能会让人感到很奇怪；但这一过程可能确实是迭代的，因为它的状态可以通过固定数目的状态变量来完全刻画，解释器在执行这一计算过程时，只需要保持这三个变量的状态就够了。

区分计算过程和写出的代码可能令人看到困惑，其中的一个原因在于一部分常见的编程语言的实现中，在执行递归的过程时，所需要消耗的内存总是与过程调用的深度成正比，即使这个过程所描述的计算过程从原理上看上去是迭代的。作为这一设计的后果，要在这些语言中描述迭代过程，必须借助于特殊的「循环结构」，例如 for 和 while 等。

而在 Scheme 的实现中则没有这一缺陷，它总是能在常亮的内存消耗中执行迭代型的计算过程，即使这一计算过程是用一个递归过程描述的。具有这一特征的编程语言实现被称为「尾递归」的，有了支持尾递归的实现，我们就可以利用常规的过程调用机制来表述迭代，而不必借助专用的迭代结构。

1.2.2 树状递归

线性递归之外的另一种计算模式是「树状递归」，作为例子来考虑斐波那契数量的计算，除了前两位是 0 和 1 之外，其他的每个数都是前两个数之和。在 Lisp 中，我们可以简单地将 n 大于 1 的 fib(n) 表示为 fib(n - 1) + fib(n - 2).

当我们计算 fib(5) 的时候，我们需要计算 fib(4) 和 fib(3), 而为了计算 fib(4) 又需要计算 fib(2), 这一展开过程将会是树状的，在每一层会形成两个分支，直到其中一个是 fib(1) 或 fib(0).

这是一个典型的树状递归，但确实一种糟糕的计算斐波那契数列的方式，因为它进行了大量的冗余计算。该过程的计算步骤将会随着 n 呈指数增长，而空间需求则正比于 n, 因为在计算中的任何一点，只需要保存树中位于该节点之上的节点的轨迹。一般来说，树状递归中的计算步骤正比于树中的节点数，空间需求正比于树的最大深度。

如果用迭代方式重新实现 fib, 将会减少大量步骤，并减少一些空间需求，但并不是说树状递归是没有价值的。当在层次性的数据结构上进行操作时，树状递归是一种非常自然而威力强大的工具。而且它更加简单直接，如果将 fib 规划为迭代过程，则必须意识到，这一计算过程是通过三个状态变量来刻画的。

对待冗余计算的一种途径是通过重新安排，使计算过程能够自动构造出一个已经计算出的值的缓存，每次要求对某一参数调用过程时，先检查这个值是否在缓存中，如果存在就可以避免重复计算。

1.2.3 增长的阶

不同的计算过程在资源的消耗上存在着巨大的差别，衡量这种差别的一种方法就是用「增长阶」的记法。令 n 是有关问题规模的一个度量，例如如果是求一个数的平方根，n 就可以是所需的精度的位数。

而 R(n) 就是当问题规模为 n 时所需的资源的量。可能是所用到的寄存器的个数，也可能是需要执行的机器指令的个数，在每一时刻执行执行固定数目的操作的计算机里，所需的时间正比于需要执行的机器执行的条数。

如果存在常数 k1 和 k2, 使得 R(n) 总是在 k1 * f(n) 和 k2 * f(n) 之间，那我们就称 R(n) 具有 O(f(n)) 的增长阶。

举例来说，前文中计算阶乘的线性递归过程中，计算步骤的数目正比于 n, 也就是说具有 O(n) 的增长阶，其空间需求的增长阶也是 O(n). 而迭代版本的阶乘，步数具有 O(n) 的增长阶，而空间是 O(1), 即为一个常数。

增长阶是对计算过程的行为的一个粗略描述，如果一个三个计算过程分别需要 n^2, 1000 * n^2, 3 * n^2 * 10 * 10 + 17, 它们的增长阶都是 O(n^2).

增长阶为我们在问题规模改变时，预计一个计算过程的行为变化提供了有用的线索。对于一个增长阶为 O(n) 的计算过程，规模增大一倍将使它所用的资源也增加一倍。对于一个 O(n^2) 的计算过程，问题规模每增加一，都将导致所用资源按倍增长。而对于 O(log n) 的计算过程，问题规模每增加一倍，所需资源只增加一个常数。

1.2.4 求幂

考虑对一个给定的数计算幂乘，一个简单的做法是将其定义为一个递归过程 expt(x, n): x * expt(x, n - 1) 直到 n 为 0 时 expt(0) 为 1. 这个线性递归计算需要 O(n) 的计算步骤和 O(n) 的空间。

如果像阶乘一样将其转换为一个等价的迭代算法，则需要 O(n) 的计算步骤和 O(1) 的空间。

因为 x^a * x^b 等于 x ^ (a + b) 所以我们可以利用这个规则将 expt(x, n) 定义成当 n 是偶数时为 expt(x, (n / 2)) ^ 2, 奇数时为 x * expt(x, n - 1). 这个算法在时间上和空间上都有 O(log n) 的增长阶，在计算 x ^ 2n 时只比 x ^ n 多一次乘法。

随着 n 的变大，O(log n) 与 O(n^2) 之间的差距会越来越大。

1.2.5 最大公约数

1.2.6 实例：质数检测

费马检查与我们前面熟悉的算法都不一样，前面的算法都保证了结果一定正确，而费马检查得到的结果只有概率上的正确性。如果一个数不能够通过费马检查，我们可以确定它一定不是质数，但如果一个数通过了费马检查，我们只能认为它有很大的可能性是质数。如果执行这个检查的次数足够多，就可以将这一检查出错的概率减少到可以接受的程度。这类算法被称为「概率算法」。