范围
第一章 构造过程抽象
1.2 节，过程和它们所产生的计算。考察计算过程的局部演化方式，研究计算过程消耗资源（时间和空间资源）的速率。P20 - 37
keywords：线性递归、迭代、树形递归、增长的阶、概率算法
算法：斐波那契数列、利用三倍角公式求正弦、分治法求幂、辗转相除法求GCD、费马小定理检查测质数
笔记
在上一节，我们已经考虑了程序设计的基本要素：
- 基本算术操作
- 组合这些基本操作定义符合过程
- 对复合过程进行抽象
即使知道了这些，我们还不能说已经理解了如何去编程序。这个阶段就好像在学下象棋，知道了每个棋子的移动规则，但却还不知道基本的开局、战术和策略。
像初学象棋者一样，我们还不知道编程领域中各种有用的常见模式。要想成为专家，我们就需要去学习看清不同的过程会产生什么样子的计算过程，考察一些过程产生的计算过程的局部演化方式，也可以说是形状。还将研究这些计算过程消耗的时间和空间资源。
1.2.1 线性递归和迭代
“如果有程序员用递归写阶乘，我直接把他开除。” —— 好像是在某人代码大全读书笔记上看到的片段
递归计算阶乘：
1 | (define (factorial n) |
线性迭代计算阶乘：
1 | (define (factorial n) |
对两个计算过程做一个比较，考虑两个计算过程的“形状”，会发现有很大的不同。
递归是一个经常在计算机学科中各门课、各种书籍中出现的字眼。我觉得在这本书里对递归的解释非常地到位以及准确。
线性递归过程
- 线性递归这一过程揭示的是先逐步展开而后收缩的过程。整个计算过程构造成一个由一系列推迟进行操作所构成的链条，收缩阶段表现为之前积累下来的运算的实际运行。
- 对于递归计算过程而言，这里还存在着另外的一些“隐含信息”，它们并未保存在变量里，而是由解释器维持着。为了执行这种计算过程，解释器就需要维护好哪些以后要执行的操作的轨迹（栈的概念）。这个链条越长（递归的深度越深），需要保存的信息就越多。
- 用这种方法计算 n 的阶乘，推迟执行的乘法链条长度正比于 n
- 当我们说一个过程是递归的时候，论述的是这一个过程语法形式上的一种事实——过程的定义中（直接或间接地）调用了自己。而当我们说一个计算过程具有递归形式（例如线性递归）的时候，我们说的是这一计算过程的实际进展方式，而不是其书写上的语法形式。
迭代计算过程
- 第二个计算过程里没有任何的增长or收缩。
- 状态可以用固定数目的状态描述变量（
product描述累计结果，counter描述何时结束迭代）描述的计算过程。 - 用这种方法计算阶乘，所需要的计算步骤正比于 n
- 在迭代的情况里，在计算过程中的任何一点，那几个状态描述变量提供了有关计算状态的一个完整描述。
- 对于递归的计算过程，这里面存在的隐含信息，它们未保存在变量里，而是由解释器维持着。这个链条越长，需要保存的信息也就越多。
- 因此，常见语言的大部分实现中，对于递归过程的解释，所消耗的内存与过程调用的数量成正比。
- 尾递归，通常被视为一种编译技巧。即：递归调用都在每次函数调用的尾部，可以被编译器优化成迭代。
1.2.2 树形递归
求斐波那契数列Fib(n)，如果采用最基础的定义翻译过来的递归过程：
1 | (define (fib n) |
会产生树形递归，每个调用中两次递归调用了自身。这是一种很糟糕的方式，因为做了过多的冗余计算。
不难证明，这一过程中，计算 (fib 1) 和 (fib 0) 的次数（也就是上面递归树的叶子个数）正好是 Fib(n+1)。而Fib(n) 的增长对于 n 来说是指数级的：Fib(n) 就是最接近黄金分割率的 n 次方除以根号 5 的整数，其中黄金分割率为：
$$ \phi = (1 + \sqrt {5} / 2 $$
简单来说，树形递归的计算步骤将随着输入的增长而指数性增长。
因此，需要规划出一个线性迭代过程。用 a 和 b 表示 Fib(1) = 1 和 Fib(0) = 0，然后反复使用这两条规则：a = a + b/b = a。不难证明，经过 n 次变换， a 和 b 分别等于 Fib(n + 1) 和 Fib(n)
1 | (define (fib n) |
1.2.3 增长的阶
不同的计算过程在计算资源的消耗上存在巨大差异。这里略微复习到算法与数据结构中复杂度的知识。
1.2.4 分治法求幂
求 b 的 n 次方。如果将 n 个 b 连乘，复杂度是 θ(n)，但有更少步数求幂的方法。
1 | b^n = b^(n/2) * b^(n/2) # n 是偶数 |
可以把复杂度从 θ(n) 降到 θ(log n)
1.2.5 最大公约数 Greatest Common Divisor
r 如果是 a 除以 b 的余数，那么 a 与 b 的公约数正好也是 b 与 r 的公约数。
GCD(a, b) = GCD(b, r)
1 | (define (gcd a b) |
remainder 是基础过程，求余。
欧几里得算法是一个高效的算法，这里有一条神奇的 Lame 定理：
如果欧几里得算法需要 K 步 计算出一对整数的 GCD，那么这对数中较小的那个数必然大于或等于第 K 个斐波那契数
证明略（或许以后会补
利用这一定理，证明：若 n 是 GCD 两个参数中较小的那个，计算过程需要 k 步，则有 $ n ≥ Fib(k) = \phi^k / \sqrt 5 $，步数 k 的增长是 n 的对数，所以算法增长的阶是 O(log n) 的。
1.2.6 用费马检查来进行质数检测
基本方法：检测 n 是不是质数，从 1 到 根号 n 之间检查因子。需要 θ(根号n) 的复杂度。但有比此更快的 θ(log n) 的方法。是基于数论中著名的费马小定理的结果。
假如 a 是整数，n 是质数，且 a,n 互质（即两者只有一个公约数1），那么a的(n-1)次方除以n的余数恒等于1。a^(n-1) mod n == 1
1 | 例如，5是质数，费马检查的过程是： |
我们要验证一个数 n 是不是质数，取任意整数（注意这里的a不用取互质的） a < n 计算 a^(n-1) mod n 如果不等于 1，那么 n 就肯定不是质数。如果等于 1，就对 n 是质数有了信心，再通过检查更多的 a 值，我们就可以不断确信 n 是一个质数。这个方法叫做费马检查，是有名的概率算法。概率算法的意思是，例如一个数通过了多轮的费马检查，但不能给出百分百确定这个数就是素数的结果，但是能给出一个概率上有信心的结果。而不是素数的数，用此方法很快就能检测出其非素性。
虽然说有一些能够骗过费马检查的整数，被称为 Carmichael 数，例如 561、1105、1729、2465。由于这些数很罕见，“撞上能够欺骗费马检查的值的机会比宇宙射线导致计算机执行出错的机会还要小”，因此费马检查还是很可靠的。
- 最惊人的应用是在密码学中，对于 200 位长度的因数分解在计算上还是不现实的，但费马检查可以在很短的时间内判断这个数的素性。
1 |
|