1.2 Procedures and the Processes They Generate - CloneableX/SICP-learning GitHub Wiki

此时我们可以思考一些关于程序中包含的元素，首先我们学习了基本的数学运算，并且把它们进行了组合以及抽象，但这并不表示我们已经掌握编程的技艺。我们目前的水平就像刚掌握象棋规则，却还不知道如何下一盘完整的棋的人，毕竟其中还包含着诸多不同情况下的不同策略。我们尚未掌握在不同情形下是否需要定义程式的判断力，以及对其结果预判的能力。

通过思维想象程式的运算结果是成为杰出程序员的重要能力。就像如果要成为一名出色的摄影师，一定需要掌握如何观察场景，场景每个区域的光影效果一样，当一名摄影师掌握这些能力后他也将变得杰出。不过在程序的世界中，变得杰出需要预见运行过程产生的结果，以及掌控程序运行的过程。于是我们要学会想象不同类型的程式所运行的过程，只有掌握了相应的技能后，我们才能构建出符合期望的程序。

程式属于运算过程的 局部演化（local evolution） 模式，它能够清晰地表现每一阶段的过程是如何构建在前一个过程之上的。从全局环境来说，一个过程的行为已经由一个程式的局部演化指定。通常来说这难以做到，但我们还是可以尽量尝试描述一些过程演化的典型情况。

在这本节的内容中，我们将研究一些由常规程式产生的过程的通用结构，同时还会关注这些过程所消耗的时间、空间相关的计算资源。我们研究的程式将十分简单，它们如同摄影中的实验品，只作为简化过的原型出现，而不是其实例。

我们以下面的阶乘函数开始本节内容：

对阶乘的运算有许多方法，其中一种方式是将 n! 分解为 n 与 (n - 1)! 的乘积，于是 n! 便转化为计算 (n - 1)! 的结果，另外需要说明的 1! 结果为 1，所以使用程式表达阶乘如下：

(define (factorial n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))

接着我们用替换模型解析 6! 的运算过程，如下图：

现在我们再以另一个视角观察如何计算阶乘。除了上述方式我们也可以将阶乘描述为，先计算 1 与 2 的乘积，再将结果与 3 相乘，接着再将结果与 4 相乘，以此类推，直到与 n 相乘为止。更正式的说法是，我们需要维护一个变动的乘积结果，以及一个从 1 数到 n 的计数器，而最终的结果就是当计数器数 n 时的乘积结果，伪代码形式如下：

product <- counter * product
counter <- counter + 1

接下来我们要将上述对阶乘的描述改写为程式，如下：

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* product counter)
                 (+ counter 1)
                 max-count)))

接着依然用替换模型解析此程式的运算过程，如下图：

比较两个过程，它们没什么不同，两个过程都以相同的数学函数为基础运算，并且运算规模与 n 都成正比。并且两个过程都产生了相同的乘法序列，然后也计算得到了相同的中间值，但另一方面，我们又认为两个过程在呈现形态上确实有所不同。

回到第一个过程的图示，通过替换模型解析的形状为先展开再收缩，如同一枚箭头。其中展开发生在过程构建 延迟操作（deferred operation） 的链条上（实际上就是乘法链条上），而收缩发生在实际执行时。建构这种延迟操作的过程称为 递归过程（recursive process），它需要解释器对稍后将执行的操作保持追踪。在计算 n! 的过程中，展开的乘法链长度就是解释器需要追踪的信息量，它随着 n 线性递增，所以这个过程也叫做 线性递归过程（linear recursive process）。

与之对比，第二个过程并没有展开，也没有收缩。运算过程的每一步只需要追踪 product、counter 和 max-count 的值即可，我们称这种过程为 迭代过程（iterative process）。通常来说，迭代过程的状态只需要通过少量状态变量存储即可，而状态变量会在迭代过程的运算中不断被更新，直到触发迭代过程结束的规则。因为在计算 n! 时此过程的步骤数随 n 线性增长，所以也被称作 线性迭代过程（linear iterative process）。

我们也可以从另一角度对比上述两个过程。在迭代过程中，运算过程的每一步都完整地记录了当时程序的状态，如果在中间步骤停止程序，再重启程序时只需要向解释器提供对应的 3 个变量值即可。而递归过程却无法做到，因为递归过程中存在一些隐藏信息，这些信息标识着过程当前的步骤，但这些信息并没有包含在程序中，而是由解释器维护。于是递归过程会产生更长的运算链条，也有更多的信息需要被解释器维护。

在这些对比中，我们要小心别将关于递归过程和递归程式的观点混淆。当我们说递归程式时，是指在编程语法上一个程式在程式体内部调用了自己，但当谈到递归过程时是从模型的角度出发，是在讨论运算过程如何演化，而不是程式语法如何书写。就如同程式 fact-iter 是递归程式，却是迭代过程一般。

另外还有个原因也容易导致大家将过程和程式混淆，许多通用语言（包括 Ada、Pascal 和 C）的实现被设计为，无论是迭代或递归占用存储的量都随着程式占用的数量而增长。如果这些语言要描述迭代过程只能通过一些特殊的循环结构，比如 repeat、until、for 和 while。在第五章关于 Scheme 的实现中我们要避免类似的缺陷。它将在一个恒定空间执行迭代过程，即使此过程是由递归程式描述的。这种属性的实现称为 尾递归（tail-recursive）。随着尾递归的实现，迭代也可以通过原有的程式调用机制应用，而那些特殊的迭代结构只是作为语法糖使用。

还有一种计算的常见模式叫做 树形递归（tree recursion）。我们以计算斐波那契数列为例，数列中的每个数都是它在数列中前两个数字之和，如下：

0, 1, 1, 2, 3, 5, 8, 13, 21...

通常斐波那契数列在数学上做如下定义：

我们立即将其转换为程式：

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

解析一下它的运算模式。当计算 (fib 5) 时，程式需要计算 (fib 4) 和 (fib 3)，计算 (fib 4) 时，需要计算 (fib 3) 和 (fib 2)。这种运算过程看过来与树十分相似，如同下图。要注意的是在每个层级都存在两个分支（除了树的最底层外），其中反应出 fib 程式在每次调用时都会调用自身两次。

此程式通常只是作为树形递归的案例使用，因为这种实现方式会产生大量的冗余运算，过于糟糕。如同上图中 (fib 3) 的重复运算占用了几乎近一半的工作量，(fib 1) 和 (fib 0) 总共被计算了 Fib(n + 1) 次，而 Fib(n) 的值呈指数级增长，更准确地说 Fib(n) 与 接近，其中

它也被称为黄金比率，满足下列等式。

所以树形递归过程的步骤数量也是根据输入参数指数级增长的，不过它消耗的空间只会以线性增长，因为树形中当前节点的计算只需要能够追踪此节点之上未计算的节点即可。通常来说，树形递归过程的运算步骤数与树的节点数量呈正比率，而占用的存储空间与树的最大深度呈正比率。

我们也可以为斐波那契数列的计算定制相应的交互过程。想象此时有一对数字 a 和 b，分别将其初始化为 Fib(1) = 1 和 Fib(0) = 0，然后重复应用下列数值转换：

a <- a + b
b <- a

不难想象，当应用上述转换 n 次后 a 与 b 便分别等于 Fib(n + 1) 和 Fib(n)，将其转换为程式如下：

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b)
                a
                (- count 1))))

计算 Fib(n) 的第二种方式是一个线性迭代过程，此过程的运算步骤只随输入数字 n 线性增长，相比前树形递归的方式它的运算步骤增长更慢。

不过并不能因为上述效率问题便断定树形递归无用，当我们思考继承结构数据的运算过程时，树形结构将成为十分强力的工具。即使如此，在数字类型的数据运算中，它也能够帮助我们思考和理解程序的设计。比如，尽管第一个计算斐波那契数列的程式比第二个更加低效，但是将斐波那契数列的数学定义转换为第一个程式更为直观。

思考迭代算法计算斐波那契数字的方式需要多花费一些精力，下面我们转换一下头脑。我们需要思考一个问题，如果提供一些 0.5 美元、25 美分、10 美分、5 美分及 1 便士，你有多少种方式可以将 1 美元兑换为同等价值的零钱？按照常规思路，我们能够编写一个程式计算出兑换零钱的方法数量吗？

其实我们可以通过递归程式解决此问题，假设不同类型的零钱按照一定顺序排列，下列关系便成立：

使用 n 种零钱兑换价值为 a 的钱币的方式数量为

• 除第一种零钱外其他种类零钱兑换为 a 的方法数加上
• 第一种零钱的面值 d 与 n 种零钱兑换为 a 的方法数

先分析上述关系为何成立，兑换零钱的方式可以分为两组，一组为不使用任何第一种零钱的方式，另一组为使用第一种零钱的方式。所以兑换零钱的方法数就等于这两组兑换零钱的方法数量相加，而后一组兑换策略的方法数量等于使用一枚第一种零钱与所有零钱的组合兑换的方法数量。

因此，我们可以将兑换零钱的问题拆分为多个用更少种类零钱兑换更小数目货币的问题。接着还要仔细思考精减规则，方便我们写出合适的算法，下列是精减后的规则：

• 如果 a 大于 0，需要为兑换方式加 1
• 如果 a 小于 0，兑换方式加 0
• 如果 n 等于 0，兑换方式加 0

我们能够轻易地将上述规则转换为程式：

(define (count-change amount) (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

first-denomination 根据传入的可用的零钱种类数量返回第一种零钱面值，目前我们认为零钱按由大到小的顺序摆放，不过任何顺序都不影响。此时我们便可以回答一开始提出的问题，使用上述程式计算：

(count-change 100)
292

兑换 1 美元的方式总共有 292 种。count-change 产生的也是树形递归过程，与第一次实现的 fib 程式一样，它也产生了大量的冗余计算（所以当它计算出最终的结果前需要花费一些时间）。不过目前也没有更好的办法解决零钱兑换问题，我们将其留做挑战后续再谈。通过这些例子我们发现，虽然树形递归比较低效，但它更加直观，我们可以将它视为引导人们思考解决问题的良好开端，在此基础上人们可以设计出更高效的程式解决同样的问题。

上述的例子已经说明不同的运算过程将导致不同的计算资源消耗，通过 增长趋势（order of growth） 的方式便于粗略估计计算过程消耗的计算资源与输入之间的关系。

如果 n 是描述一个问题大小的参数，那 便是运算过程解答此问题时需要消耗的资源大小。虽然上述例子是以 n 作为程式的输入进行说明，但 n 可能是隐含在输入参数的条件中。比如，如果我们打算通过逼近方式求取平方根，n 可能是平方根结果要求的精确值。再举一个例子，如果要计算矩阵乘法，n 可能是矩阵的行数。总而言之，一个问题中肯定有一些元素对分析运算过程起着决定性的作用。与之类似， 估算的可能是内部存储寄存器的使用量，也可能估算的是初始机器命令的执行次数等等。在一次只执行固定数量操作的计算机中，运算所消耗的时间与机器的操作数有紧密关系。

当我们说 存在增长趋势 （可写作 ） 时，如果存在与 n 无关的正整数 和 ，对于任何足够大的 n 都有 。

例如，通过线性递归过程计算阶乘时，运算步数与输入参数 n 存在关系，其运算步数增长趋势为 ，占用的空间也为 。迭代过程计算阶乘时虽然运算步数也是 ，但空间占用为 ， 表示常量。树形递归计算斐波那契数列时需要 步和 空间，其中 是黄金比率。

增长趋势只是一种粗糙地描述过程行为的方式。比如，需要 步、 步和 步的过程增长趋势都是 ，但增长趋势在一定程度上明确了当修改问题规模时我们对过程变化的期望。对于 （线性）过程，当问题规模翻倍时运算过程消耗的计算资源也将翻倍，而对于指数型的过程来说，每当问题规模扩大运算过程消耗的资源也将成固定倍数地增长。在本章的余下内容中，我们还将研究两种呈对数增长趋势的算法，这种运算过程在问题规模成倍增长时对资源消耗的增长会按固定量增加。

如果要通过程式计算一个数字的多次幂结果，首先需要为程式提供底数 b 和指数 n 并依此参数计算 ，并且按下列的递归定义缩写程式：

翻译为程式如下：

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

上述程式属于线性递归过程，时间和空间的增长趋势都为 。不过像计算阶乘一样，我们要为求幂计算定制一个采用线性迭代的程式：

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product))))

这个程式拥有 的时间增长趋势和 的空间增长趋势。

我们还可以通过连续平方的方式求多次幂，比如求 的结果，可以拆解为：

也可以将其转换为三组平方的结果：

看起来连续平方的方式求幂效果不错，我们试着用规则描述它，如：

如果 n 是偶数

如果 n 是奇数

接下来将此规则转换为程式：

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expr b (/ n 2))))
        (else (* b (fast-expr b (- n 1))))))

其中的判断是否偶数的谓词通过基本程式 remainder 定义：

(define (even? n)
  (= (remainder n 2) 0))

改进后求幂程式时间和空间增长趋势都与 n 呈对数关系。我们观察程式，如果要计算只需要得到的值，因为求幂的幂数增长需要增加双倍的乘法操作，所以求 n 次幂的时间增长趋势与以 2 为底的 n 的对数相关，也就是增长趋势为。

与不同，在 n 增大时更加收敛。对于 fast-expt 来说，当 n = 1000 时只需要相乘 14 次即可得到结果。同样你可以按照此思路将其改造为对数级时间增长趋势的迭代过程，就像其他例子中的迭代算法一样，你无法直接从递归过程修改而是需要一些智慧。

最大公约数（以下简称 GCD）表示两个整数 a 和 b 都能够整除的最大整数，比如 16 和 28 的 GCD 是 4。第二章在研究有理数算法时也需要计算 GCD 将其约分至最简情况（如果要约分至最简情况需要将分子和分母都除以 GCD，比如 16/28 约分至最简情况为 4/7）。计算 GCD 的其中一种方法为查找两个整数的公因数，这种方法效率极高。

这种算法是基于一个发现，如果 r 是 a 除以 b 的余数，那么 a 与 b 同 b 与 r 有类似的公约数，于是可以得到以下等式：

GCD(a, b) = GCD(b, r)

通过不断计算缩小的一组数的 GCD 得到最终的结果，例如：

GCD(206, 40) = GCD(40, 6)
             = GCD(6, 4)
             = GCD(4, 2)
             = GCD(2, 0)
             = 2

当 GCD(206, 40) 收敛为 GCD(2, 0) 时得到其 GCD 为 2。将两个正整数通过不断相除取余的方式计算，直到某组数据的第二个数字为 0 时结束，GCD 就是这组数据的第一个数字，这就是著名的 Eculid 算法。

将此算法用程式表达如下：

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

此程式产生的是迭代过程，时间增长趋势为对数级，并且与斐波那契数列有奇妙的联系。

拉梅定理：如果 Euclid 算法需要 k 步计算得到一组正整数的 GCD，那么此组数据中较小的一个一定大于或等于第 k 个斐波那契数。

通过上述定理我们可以估算 Euclid 算法的增长趋势。假设 n 是程式两个入参中较小的一个，如果运算过程花费 k 步，则一定存在 ，所以运算步数 k 等于以 为底 n 的对数，得出增长趋势为 。

本节内容将描述两种素数的检测方法，其中一种增长趋势为 ，而另一种属于概率算法，增长趋势为 ，本节结尾的练习建议以这些算法为基础进行。

在古代，数学家早已沉迷素数问题的研究，并且许多人致力于素数的检测方法的研究，其中一种方法是通过查找给定数的约数判定其是否为素数，下面的程序可以帮助我们找到关于给定数 n 的比 1 大的最小约数。该程式是通过与以 2 开始的连续整数相除查找约数，如下：

(define (smallest-divisor n) (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b) (= (remainder b a) 0))

如果一个数除自身和 1 之外还存在其他约数则不是素数，程式如下：

(define (prime? n)
  (= n (smallest-divisor n)))

find-divisor 程式的检测以基于这样一个事实，如果 n 不是素数，则它必然存在小于 的约数。也就是说，程式只需要在 1 与 间找出 n 的约数，所以此程式的增长趋势为 。

这种增长趋势为 的概率检测方式是基于费马小定理。

费马小定理：如果 n 是素数，a 为任意小于 n 的正整数，a 的 n 次方与 a 与 n 取模的值全等。

与 n 取模的值全等是指两个数除以 n 的余数相同，而 a 除以 n 的余数就是 a 与 n 取模的余数，所以简称 a 与 n 取模。

如果 n 不是素数，通常来说满足 a < n 条件的大多数正整数都无法满足上述条件，这也就导出下面的概率检测算法。给定数字 n，随机取数 a，使 a 满足条件 a < n，然后计算 与 n 取模。如果结果不等于 a，n 一定不是素数；如果结果为 a，n 有较大机率为素数。接着再获取另一个随机数并用同样的方法检测，如果结果依然是等于此随机数，我们将更加相信 n 是素数。随着检测次数的上升我们也更加相信 n 是素数。这便是著名的费马检测。

要实现费马检测需要首先计算一个数的多次幂与另一个数的取模结果：

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder 
           (square (expmod base (/ exp 2) m))
           m))
        (else
          (remainder
            (* base (expmod base (- exp 1) m))
            m))))

这与 fast-expt 程式十分相似，它也使用了连续平方的方式，所以增长趋势为以相应幂次为底的对数。

费马检测在 1 至 n 之间获取随机数，不过 1 与任何正整数都满足费马检测的条件，所以需要排除。我们通过 Scheme 的基础程式 random 获取随机数 a，random 将返回一个小于入参的非负整数，所以要获取 1 至 n - 1 之间的随机数需要向 random 传入 n - 1，并将获取结果加 1：

(define (fermat-test n)
  (define (try-it a)
     (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

下列程式通过传入一个参数控制费马检测的次数，如果每次费马检测都成功则结果为 true，如果其中一次失败则结果为 false。

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

费马检测与其他素数检测方式的最大区别在于它无法保证结果完全准确，也就是说费马检测只是一种可能性检测。换个说法，如果费马检测的结果为失败，我们可以断言此数不是素数，但检测通过，我们只能说此数有较高的可能性是素数，却无法保证它一定是素数。对于任何数而言，只要我们执行费马检测的次数足够多，素数检测错误的概率也就越小。

不幸的是，上述描述也并不准确。如今发现一些数字即使不是素数也依然满足费马小定理，所幸这样的数字比较罕见，总体而言费马检测依然相对可信。

现在有一些基于费马检测的变体可以避免上述数字通过检测。这些测试与费马检测类似，也是获取满足 a < n 的随机数 a，然后检测关于 a 与 n 满足的一些条件，然后通过使 n 通过多次的随机数测试提高其为素数的可能性。

这种通过降低出错概率以确保结果正确性的算法激起了人们的兴趣，大家称这种类型的算法为概率算法（probabilistic algorithms）。这片研究领域大有可为，而且很多概率算法已经应用于众多领域。