前言
在前面一节里已经考虑了程序设计中的一些要素：使用许多基本的算数过程进行操作，对这种操作进行组合，通过定义各种复合过程，对复合操作进行抽象。
这一节将学习编程领域各种有用的常见模式，获得一种值得定义那些过程的知识，并能够对执行一个过程的效果作出预期的能力。
一个过程也就是一种模式，它描述了一个计算过程的 局部演化方式 ，描述了这一计算过程中的每个步骤是怎样基于前面的步骤建立起来的。
在有一个刻画的计算过程描述之后，这里做出一些有关这个计算过程整体或者全局过程的论断。
线性递归和阶乘迭代
代换模型展示了一种先逐步展开而后收缩的形状。展开阶段，这一计算过程构造了一个 推迟执行的操作 链条；收缩阶段表现为这些运算的实际执行过程。要执行这种计算过程，解释器就需要维护好那些以后需要执行操作的轨迹。这样的计算过程称之为 线性递归过程 。
迭代计算过程。状态可以使用固定数目的状态变量描述的计算过程，与此同时，又存在一套固定的规则，描述计算从一个状态到下一个状态转换时这些变量的更新方式；还有一个可能的结束检测，它描述了这一计算过程应该终止的条件。
这里还可以从另一个过程来描述这两个过程之间的差异。在迭代的情况下，在计算过程中的任意一点，那几个程序变量都提供了有关计算状态的一个完整的描述。如果我们另上述计算在某两个步骤之间停止下来，要想重新唤醒这一计算，只需要为解释器提供有关有关这三个变量的值，而对于线性递归的计算过程，这里还存在另外一些“隐含”的信息，它们并未保存在程序变量里，而是由解释器位置。
树形递归
另外一种常见的计算模式称为树形递归。树形递归计算过程里所需要的计算步骤正比与树中的节点数。其空间需求正比于树的最大深度。
示例：
给出0.5美元、0.25美元、0.1美元、0.05美元、0.01美元的硬币，要将1美元换算成为硬币共有多少种方法。
将总数为a的现金换算成为n种硬币的不同方式的数目等于：
- 将现金数a换算成除第一种硬币之外的所有其他硬币的不同方式的数目。
- 将现金a-d换算成为所有种类的硬币的不同方式的数目，其中d是第一种硬币的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17(define (count_change x)
(cc x 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)))
(count_change 100)
增长的阶
前面的一些例子说明，不同的计算过程在消耗计算资源的速率上面可能存在巨大的差异。描述这个差异的一种方便的方式就是采用 增长的阶 的记法，以便我们去理解在输入变大的时候，某一计算过程所需资源的粗略度量情况。
这里将n作为一个参数，让它作为问题规模的一种度量，令R(n)是一个计算过程在处理规模为n的问题时所需要的资源量。在前面的例子里面，我们取n为给定函数所需要计算的那个数，当然也存在其他可能性。例如，如果我们的目标是计算出一个数的平方根的近似值，那么就可以将n取为某个所需精度的数字个数。一般而言总存在某个有关问题特性的数值，使得我们可以相对与它去分析给定的计算过程。同时R(n)可以是所用内部寄存器的数目的度量值，也可能是需要执行的机器操作数目的度量值。或者其他类似的东西。
最大公约数
lame定理 如果欧几里得算法需要K步得到一对整数的最大公约数，那么这对数中较小的必然大于或者等于第k个斐波那契数。
example：素数检测
- 寻找因子
- 费马检查： 一种通过概率检测一个数是否为素数的方法。