主要内容:

• 表达式，值，define
• 过程的内部定义和块结构(上述示例已经解释)
• 分析过程（静态，描述）产生的计算进程（动态，行为）
• 计算进程的类型
  • 线性递归
  • 线性迭代
  • 树形递归
• 计算的代价

第一部分: 表达式，值，define

1.总结表达式的一些概念

变量

如果一个变量没定义，对它求值是错误，求值中断,如果变量有定义，求值得到它当时的关联值

内部过程

对内部过程名求值得到某种特殊信息。如（不同系统可能不同）

组合过程:

对自己定义的过程名求值也得到特殊信息。

特殊形式的名字不能求值

例如，对 define 求值将出错

2.scheme的基本数值类型

数值类型

整数，如 1，17， 2035, Scheme（Racket）支持任意大的整数及其精确运算

实数，如 3.57，

其他数值类型 ……

数值类型的运算

基本算术运算：+ – * …

比较和判断（得到逻辑值）：> < … zero? even? …

常用函数：abs quotient remainder module sin …

随机数生成，如 (random 10)，(random 1.0)

布尔类型

逻辑值 #t 和 #f，逻辑运算

逻辑真表达式：#t 逻辑假表达式：#f

字符类型

写起来比较麻烦，编写简单程序时使用较少 #\a #\B #\{ #\space #\newline

字符类型的操作

字符比较：char=? char>? …

其他操作：char-upcase …

数值字符转换：char-digit digit-char …

字符串类型

“Peking University”, “Mathematics”, “information science”

字符串运算（操作）

常用操作：string-length string-ref (取串中字符)……

字符串比较：string=? string<? ……

模式匹配：(string-search-forward pattern string)……

其他：string-append (拼接) (substring mn)……

还有一些其他类型

包括下一章要讨论的组合数据类型

有关情况可以查阅语言手册和用户手册

3.define相关

define 给名字（变量名/组合过程名）建立约束值,建立什么值的情况依赖于 define 表达式的形式

给变量建立约束值

• 形式: (define 变量名 值表达式)
• 例: (define x (+ 3 (* 5 7)))
• 意义: 求出值表达式的值，给变量关联这个值

定义过程

• 形式: (define (过程名 形式参数…) 过程体表达式),
  
• 其中: 过程名是一个名字，形式参数可以有0个或多个,过程体表达式可以是多个表达式，其中可以引用形式参数
• 意义: 为过程名约束一个组合过程，其形式参数和过程体由这个define 的成分给出，这里的过程体表达式不求值

定义简单过程

(define (f x) (+ (* (- x 1) x) (* (+ x 1) (+ x 2))) )

定义多个参数的过程

(define (g m n) (+ (* m m) (* n n)) )

定义无参过程

(define (h) (…) )

注意与 (define h …) 和使用 h 之间的不同

形参的作用域是组合过程的体，在这个体里出现了形参名，就表明是引用相应的形参

第二部分: 计算过程

要真正的理解程序设计,还需要理解程序的行为.

对于一个特定的问题,大多数情况先存在许多不同的方式可以解决它,那么如何选择最合适的呢?这就需要我们必须理解程序所蕴含的计算,理解一个过程定义运行时所产生的计算过程.

在Scheme语言编程中,最重要的的一个特性就是递归的使用.所以,对于递归过程产生的计算过程我们要深入的探讨一下.而要探讨一个计算过程,我们通常是从该过程运行时的时间和空间来分析.

首先我们说一下什么是过程?

一个过程（是一个文本描述）可以看作一种计算模式，它

• 描述了一种特定计算的演化进程和方式
• 对一组适当的参数，确定了一个具体计算（一个计算进程实例，表现为一系列具体的演化步骤）
• 要完成一件工作，我们可能写出很多大不相同的过程
• 完成同一工作的两个过程导致的计算进程可能大不相同

下面通过例子讨论几个简单过程产生的计算进程的”形状”，观察其中各种资源消耗的情况（主要是时间和空间）,得到的认识可供我们在编写其他程序时参考.

首先一个例子是:阶乘计算.

一种看法（递归的观点）: n 的阶乘就是 n 乘以 n – 1 的阶乘

n! = n •(n-1) •(n-2) •…•2 •1= n •[(n-1) •…•2 •1] = n •(n-1)!

过程定义：

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

用代换模型推导

由 (factorial 6) 得到的计算进程见图

另一观点：n! 是从 1 开始顺序乘各个自然数，乘到 n 就得到结果

product ← counter * product

counter ← counter + 1

过程定义:

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

用代换模型推导

显然其计算过程如下:

二者的对比如下:

另外一种视角的线性递归和迭代的分析

在迭代计算进程中，所需的所有信息都保存在几个变量里

• 可以在计算中任何一步中断和重启
• 只要有这组变量的当前值，就可以恢复并继续计算

在线性递归中，相关变量的信息不足以反映计算进程的情况

• 解释器需要在内部保存一些”隐含”信息
• 这种信息的量随着计算进程的长度而线性增长

注意区分”递归计算进程”和”用递归方式定义的过程”

• “递归计算进程”说的是计算中的情况和执行行为,反映计算中需要维持的信息情况
• “用递归方式定义过程”说的是程序写法，在定义过程的代码里出现了对这个过程本身的调用

常规语言里都提供专门循环结构（for, while等）描述迭代计算,Scheme 采用尾递归技术，可以用递归方式描述迭代计算

尾递归形式和尾递归优化

• 一个递归定义的过程称为是尾递归的，如果其中对本过程的递归调用都是过程执行的最后一个表达式
  
• 虽然是递归定义过程，计算所需的存储却不随递归深度增加。尾递归技术就是重复使用原过程在执行栈里的存储，不另行分配
  

具体的尾递归的知识我们在后面会讲到.

树形递归

另一常见计算模式是树形递归，典型例子是Fibonacci数的计算

Fib(n) = 0 若 n = 0

= 1 若 n = 1

= Fib(n-1)+Fib(n-2) 否则

过程的定义如下:

(define (fib n)

(cond ((= n 0) 0)

((= n 1) 1)

(else (+ (fib (- n 1))

(fib (- n 2))))))

(计算过程如上图)

虽然上面的过程作为树形递归的示例具有一定的教育意义,但是也很显然是一种很糟糕的计算过程,因为fib(3)的计算过程重复两次,而fib(3)几乎占了整个计算过程的一半.

已知 Fibonacci 数 Fib(n) 的增长与 n 成指数关系（练习1.13），因此fib(n) 的计算量增长与 n 的增长成指数关系。这种情况很糟糕.

考虑 Fibonacci 数的另一算法：取变量 a 和 b，分别初始化为 Fib(0) 和 Fib(1) 的值，而后反复地同时执行更新操作：

a ← a + b

b ← a

过程定义（形成的计算进程是线性迭代）：

(define (fib n)

(define (fib-iter a b count)

(if (= count 0)

b

(fib-iter (+ a b) a (- count 1))))

(fib-iter 1 0 n))

采用递归方式写的程序可能低效，为什么还值得关心？

1. 并不必然低效
2. 有些问题用递归描述特别自然.

下人民币的硬币有1元，5角，1角，5分，2分和1分, 问题：给了一定的人民币，问有多少种不同方式将它换成硬币？

这个问题用递归方式解决比较简单和自然面一个树形递归的例子,而且思路显然是dp的思想,下面的解题思路:

首先要分析问题，规划出一种对问题的递归观点（算法）

例如：确定一种硬币排列，币值 a 换为硬币的不同方式等于：

• 将 a 换为不用第一种硬币的方式，加上
  
• 用一个第一种硬币（设币值为 b）后将 a-b 换成各种硬币的方式
  

递归的观点（递归的分析）

设法把解决原问题归结为在一定条件下解决一个/几个相对更简单的同类问题（或许还有另外的可以直接解决的问题）

例如：阶乘函数把求 n 的阶乘归结为求 n – 1 的阶乘, 把求 Fibnacchi 数 Fn 归结为求 Fn – 1 和 Fn – 2

这里把用 k 种硬币得到币值 a 归结为两个更简单的情况

• 用 k – 1 种硬币得到 a （减少一种硬币）
  
• 用 k 种硬币得到较少的币值（前面说的 a-b，减少了币值）
  

递归算法还需把问题最终归结为一种/几种能直接得到结果的基本情况

• 对阶乘，1 的阶乘是 1
  
• 对 Fibonacci 数，F0 和 F1 可以直接得到
  

换硬币的几种基本情况：

• a = 0，计 1 种方式
  
• a < 0，计 0 种方式，因为不合法
  
• 货币种类 n = 0 但 a 不是 0，计 0 种方式，因为已无货币可用
  

综合这些考虑，不难写出一个递归定义的过程, 过程定义（只计算不同换法的数目，不考虑换的方式）

<span style="font-size:12px;">① (define (count-change amount)

(cc amount 6))

②(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

(coin-value kinds-of-coins))

kinds-of-coins)))))

③ (define (coin-value kinds-of-coins)

(cond ((= kinds-of-coins 1) 1)

((= kinds-of-coins 2) 2)

((= kinds-of-coins 3) 5)

((= kinds-of-coins 4) 10)

((= kinds-of-coins 5) 50)

((= kinds-of-coins 6) 100)))</span>

实现递归计算进程的过程也有价值：

• 是某些问题的自然表示，如一些复杂数据结构操作（如树遍历）
  
• 代码通常更简单，很容易确认它们解决了原来的问题要做出与之对应的实现迭代进程的过程，可能困难得多
  

换零钱不同方式用递归描述很自然.

有时清晰简单的递归描述的计算代价很高，而对应的高效迭代过程可能很难写。人们也一直在研究：

• 能否自动地从清晰易写的程序生成出高效的程序？
  
• 如不能一般地解决这个问题，是否存在一些有价值的问题类，或一
  
• 些特定的描述方式，对它们有解决办法？
  
• 这个问题在计算机科学技术中处处可见，永远值得研究。例如，今天蓬勃发展的有关并行程序设计的研究
  

关于增长的阶知识点不在讲述,这部分其实就是算法的时间复杂度的描述.下面直接来一个示例:素数检查.

问题：判断整数 n 是否素数。下面讨论两种方法，前一个的复杂性是O(sqrt n)，另一个是概率算法，复杂性是 O(log n)

确定因子的直接方法是用顺序的整数去除。找最小因子的过程：

<span style="font-size:12px;">① (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))</span>

素数就是”大于 2 的最小因子就是其本身”的整数：

(define (prime? n)

(= n (smallest-divisor n)))

n 非素数时一定有不大于其平方根的因子。需检查 O(sqrt n) 个整数.

下面考虑的概率算法的基础是费马小定理：

若 n 是素数，a 是任小于 n 的正整数，则 a 的 n 次方与 a 模 n 同余

数 a 除以 n 的余数称为 a 取模 n 的余数，简称 a 取模 n

两个数模 n 同余：它们除以 n 的余数相同

n 不是素数时多数 a < n 都不满足上述关系

这样就得到一个”算法”

• 随机取一个 a < n，求 a^n 取模 n 的余数
  
• 如果结果不是 a，那么 n 不是素数
  
• 否则重复上述过程
  

n 通过检查的次数越多，是素数的可能性就越大,但并不能保证是素数，因此，得到的结论是概率性的

为实现这一算法，需要定义一个计算自然数的幂并取模的过程：

<span style="font-size:12px;">(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))))</span>

过程 expmod 利用了一个数学关系 :(a * b) mod c = ((a mod c) * (b mod c)) mod c

这样做，可以保证计算的中间结果不会变得太大.

执行费马检查需要随机选取 1 到 n-1 之间的数，过程 ：

(define (fermat-test n)

(define (try-it a) (= (expmod a n n) a))

(try-it (+ 1 (random (- n 1)))))

(random (- n 1)) 得到区间 [0, n-2] 中的随机数

“判断”是否素数需要反复做费马检查。把次数作为参数：

<span style="font-size:12px;">(define (fast-prime? n times)

(cond ((= times 0) true)

((fermat-test n) (fast-prime? n (- times 1)))

(else false)))</span>

在被检查的数通过了 times 次检查后返回真，否则返回假,这里的真假只有概率的意义.

上述算法只有概率意义上的正确性：随着检查次数增加，通过检查的数是素数的概率越来越大

一点说明：费马小定理只说明素数能通过费马检查,并没说通过检查的都是素数，存在不是素数但却能通过检查的数,人们已提出了其他检查方法，能保证通过检查的都是素数

这一算法的结论只在概率上有意义

• 结果只有概率意义的算法称为概率算法
  
• 概率算法已经发展成了一个重要研究领域，有许多重要应用
  
• 在实际中，很多时候也只需要有概率性的保证
  

总结

Scheme 的一些情况

• 类型和操作
  
• define 的两种情况
  

内部过程定义，方法和意义

计算进程的形状

• 线性迭代
  
• 线性递归
  
• 树形递归
  

算法复杂性