程序与递归-组合-抽象与构造.ppt

《程序与递归-组合-抽象与构造.ppt》由会员分享，可在线阅读，更多相关《程序与递归-组合-抽象与构造.ppt（56页珍藏版）》请在装配图网上搜索。

1、第 6讲 程序与递归：组合 -抽象与构造 -程序是实现系统复杂功能的一种重要手段 -程序的本质是组合、抽象与构造 -构造的基本手段是递归，一种表达相似性对象及动作 的无限性构造的方法 2/57 程序与递归：组合 -抽象与构造 1. 程序的作用和本质 ? 程序的作用和本质 -计算系统与程序 -程序：组合、抽象与构造 3/57 首先，设计并实现系统可以执行的基本动作 (可实现的 )，例如 “ 与 ” 动作 “ 或 ” 动作 “ 非 ” 动作 “ 异或 ” 动作 那么，复杂的动作呢？ 系统需要提供复杂的动作 复杂的动作千变万化 复杂的动作随使用者使用目的的不同而变化 复杂的动作是通过对基本动作进行各

2、种组合来实现的 1. 程序的作用和本质 1.1 怎样设计并实现一个计算系统 ? 如何设计实现一个基本计算系统？ 已知的基本事实是 : “ 加减乘除运算都可转换为加法运算来实现 ” “ 加法运算又可以转换为逻辑运算来实现 ” “ 基本的逻辑运算与、或、非、异或等可通 过门电路予以实现 ” 则基本计算系统可以如下实现 4/57 指令 ：控制基本动作执行的命令 “与”动 作 “或”动作 “非”动作 AND OR NOT 系统 (A AND B) AND C) OR (NOT C) 复杂动作 拆解开 X= A AND B X= X AND C Y= NOT C X= X OR Y 程序 :由基本动作指

3、令构造的， 若干指令的一个组合或一个执行 序列，用以实现复杂动作 如何设计实现一个基本计算系统？ 1.程序的作用和本质 1.2 什么是程序 ? 5/57 指令 ：控制基本动作执行的命令 “与”动 作 “或”动作 “非”动作 AND OR NOT 系统 (A AND B) AND C) OR (NOT C) 复杂动作 程序执 行机构 自动解释程序 中的各种组合 , 并按次序调用 指令 (基本动 作 )予以执行 程序 :由基本动作指令构造的， 若干指令的一个组合或一个执行 序列，用以实现复杂动作 如何设计实现一个基本的计算系统？ 1.程序的作用和本质 1.3 程序能否自动执行 ? 6/57 基本动

4、作 对基本动作的 抽象与控制 “与”动作 AND “或”动作 OR “非”动作 NOT 复杂动作 = 基本动作的各种方式的组合 (Ai XOR Bi) XOR Ci (Ai XOR Bi) AND Ci) OR (Ai AND Bi) 解释这种组合 , 并 按次序调用基本动 作予以执行 程序 执行 机构 程序 指令 计算系统 = 基本动作 + 指令 + 程序执行机构 指令 = 对可执行基本动作的抽象，即控制基本动作执行的命令 程序 = 基本动作指令的一个组合或执行序列 , 用以实现复杂的动作 程序执行机构 = 负责解释程序即解释指令之间组合，并按次序调用指令即 调用基本动作执行的机构 基 本

5、动 作 1.程序的作用和本质 1.4 计算系统与程序 ? 7/57 基本动作 对基本动作的 抽象与控制 “ 与 ” 动作 A ND “ 或 ” 动作 OR “ 非 ” 动作 N O T 解释这种组合 , 并 按次序调用基本动 作予以执行 程序 执行 机构 指令 基 本 动 作 复杂动作 = 基本动作的各种方式的组合 程序 (A i XOR B i ) XO R C i ( ( A i XOR B i ) A N D C i ) O R ( A i A N D B i ) 基本动作 对基本动作的 抽象与控制 “加”动作 + “减”动作 - “乘”动作 x “除 ”动作 复杂动作 = 基本动作的各

6、种方式的组合 (V1 + V2) x (V3 V4) V5 (V1 (V2 x (V3 + V4) - ( V5 x V6) 解释这种组合 , 并 按次序调用基本动 作予以执行 程序 程序 执行 机构 指 令 一种较高抽象层次的 系统 抽象 抽象 ： 将经常使 用的、可 由低层次 系统实现 的一些复 杂动作， 进行 命 名 ，以 作为高层 次系统的 指令被使 用 一种较低抽象层 次的 系统 1.程序的作用和本质 1.5 程序：组合 -抽象 -构造 ? 8/57 程序构造示例 (I) -运算组合式的表达 -组合、抽象与构造 -命名计算对象 和 构造中使用名字 及 计算中以计算对象替换名字 程序与

7、递归：组合 -抽象与构造 2. 程序构造示例 (I) 9/57 2. 程序构造示例 (I) 2.1 运算组合式 ? (100 + 205) 由数值，到基本运算组合式 中缀表示法 , 用运算符 (即前述的指令 ) 将两个数值组合起来，运算符在中间 (+ 100 205) 100 205 实际的数值 前缀表示法 , 用运算符 (即前述的指令 ) 将两个数值组合起来，运算符在前面 将运算符表示的操作应用于后面的一组数值上，求出结果 (+ 100 205 300 400 51 304) 一个运算符可以表示连加，连减等情况， 10/57 (+ 100 205) (- 200 50) (* 200 5)

8、(* 20 5 4 2) (- 20 5 4 2) (+ 20 5 4 2) 一起练习 ,书写程序 , 由数值，到基本运算组合式 2. 程序构造示例 (I) 2.1 运算组合式 ? 11/57 运算组合式的 “ 嵌套 ” 及其计算过程 (+ 100 205) (+ (+ 60 40) (- 305 100) (* (* 3 (+ (* 2 4) (+ 3 5) (+ (- 10 7) 6) 计算过程 (* (* 3 (+ (* 2 4) (+ 3 5) (+ (- 10 7) 6) (* (* 3 (+ 8 8) (+ 3 6) (* (* 3 16) 9 ) (* 48 9 ) 432 2.

9、 程序构造示例 (I) 2.2 如何构造运算组合式 -组合 12/57 (define height 2) (+ (+ height 40) (- 305 height) 名字的定义：定义名字 height与 2关联 , 以后可以用 height来表示 2 一种类型的名字：数值型的名字 (+ (* 50 height) (- 100 height) 名字的使用 注意：不同类型的对象可以有不同的定义方法。这里统一用 define 来表示，在具体的程序设计语言中是用不同的方法来定义的 命名计算对象 和 构造中使用名字 及 计算中以计算对象替换名字 2. 程序构造示例 (I) 2.3 如何用名字简化

10、运算组合式的构造 ?-抽象 13/57 (define pi 3.14159) (define radius 10) (* pi (* radius radius) (define circumference (* 2 pi radius) (* circmference 20) 命名计算对象 和 构造中使用名字 及 计算中以计算对象替换名字 2. 程序构造示例 (I) 2.3 如何用名字简化运算组合式的构造 ?-抽象 14/57 程序构造示例 (II) -组合、抽象与构造 -命名新运算符 和 构造中使用新运 算符 及 执行中以过程替换新运算符 -带有条件的运算组合式 程序与递归：组合 -抽象

11、与构造 3. 程序构造示例 (II) 15/57 (define (square x) (* x x) 名字的定义：定义名字 square为一个 新的运算，即过程或称函数 另一种类型的名字：运算符型的名字 名字的使用 注意：不同类型的对象可以有不同的定义方法。这里统一用 define 来表示，在具体的程序设计语言中是用不同的方法来定义的 新运算符，即过程名或函数名 形式参数， 使用时将被实 际参数所替代 过程体，用于表示新运算符的具体计 算规则，其为关于形式参数 x的一种 计算组合。 (square 3) (square 6) x2 命名新运算符 和 构造中使用新运算符 及 执行中以过程替换新

12、运算符 3. 程序构造示例 (II) 3.1 如何用名字简化运算组合式的构造 ?-抽象 16/57 名字的使用 (square 10) (square (+ 2 8) (square (square 3) (square (square (+ 2 5) (define (SumOfSquare x y) (+ (square x) (square y) (SumOfSquare 3 4) (+ (SumOfSquare 3 4) height) x2+y2 命名新运算符 和 构造中使用新运算符 及 执行中以过程替换新运算符 3. 程序构造示例 (II) 3.2 程序构造 组合与抽象 17/57

13、 (define (NewProc a) (SumOfSquare (+ a 1) (* a 2) (NewProc 3) (NewProc (+ 3 1) (a+1)2+(a*2)2 命名新运算符 和 构造中使用新运算符 及 执行中以过程替换新运算符 3. 程序构造示例 (II) 3.2 程序构造 组合与抽象 18/57 (NewProc (+ 3 1)的两种计算过程示意 (NewProc (+ 3 1) (NewProc 4) (SumOfSquare (+ 4 1) (* 4 2) (SumOfSquare 5 8) (+ (Square 5) (Square 8) (+ (* 5 5)

14、 (* 8 8) (+ 25 64) 89 先求值，再代入 含名字的运算组合式的计算方法：求值、代入、计算 命名新运算符 和 构造中使用新运算符 及 执行中以过程替换新运算符 3. 程序构造示例 (II) 3.3 构造程序的执行 求值、代入与计算 19/57 (NewProc (+ 3 1)的两种计算过程示意 (NewProc (+ 3 1) (SumOfSquare(+ (+ 3 1) 1) (* (+ 3 1) 2) (+ (Square (+ (+ 3 1) 1) (Square (* (+ 3 1) 2) 89 (+ (* (+ (+ 3 1) 1) (+ (+ 3 1) 1) (*

15、(* (+ 3 1) 2) (* (+ 3 1) 2) (+ (* (+ 4 1) (+ 4 1) (* (* 4 2) (* 4 2) (+ (* 5 5) (* 8 8) (+ 25 64) 先代入， 后求值 代入阶段 求值阶段 含名字的运算组合式的计算方法：代入、 求值、 计算 命名新运算符 和 构造中使用新运算符 及 执行中以过程替换新运算符 3. 程序构造示例 (II) 3.3 构造程序的执行 求值、代入与计算 20/57 (cond ( ) ( ) . ( ) ) (define (abs x) (cond ( x 0) x) (= x 0) 0) ( x 0) (- x) 3.

16、程序构造示例 (II) 3.4 有条件的运算如何表达 ? 带有条件的运算组合式 21/57 问题 1：用前缀表示法书写下述表达式 10 + 4 + (8- (12 - (6 + 45) 3*(6-2)(12-7) 问题 2：请定义一个过程，求某一数值的立方 a3 问题 3：进一步以问题 2定义的过程，再定义一个 过程，求某两个数值的立方和。 进一步 求 ，并模拟给出计算过程。 a3+b3 53+83 3. 程序构造示例 (II) 3.5 你能表达与构造程序吗 ? 22/57 0 00 0 )( 2 2 xifxx xif xifxx xf (cond ( ) ( ) . ( ) ) (defi

17、ne (f x) (cond ( x 0) (- (Square x) x) (= x 0) 0) (=1时 等比数列递推公式 a0=5 an=an-1 20 当 n=1时 第 1项 (或前 K项 )的值是已知的 递推基础 ； 由第 n项或前 n项计算第 n+1项 递推规则 /递推步骤 ； 由前向后，可依次计算每一项 等差数列的产生 a0=5 a1=a0+3 = 8 a2=a1+3 = 11 a3=a2+3 = 14 a4=a3+3 = 17 28/57 28 数学中的数学归纳法 数学归纳法是一种用于证明与自然数有关的命题正确性的证明方法 ， 该方 法能用有限的步骤解决无穷对象的论证问题 。

18、由归纳基础和归纳步骤构成： 假定对一切正整数 n, 有一个命题 P(n),若以下证明成立 , 则 P(n)为真 。 (1)归纳基础 : 证明 P(1)为真； (2)归纳步骤 : 证明对任意的 i， 若 P(i)为真 ， 则 P(i+1)也为真 。 证明 : (1)归纳基础 : 当 n=1时 , 等式成立即 1=1; (2)归纳步骤 : 设对任意 k, P(k)成立 , 即 1+3+5+ +(2K-1)=K2. 则 P(K+1) = 1+3+5+ + (2K-1) + (2(K+1)-1) = K2+2K+1=(K+1)2 ，则当 P(k) 成立时 P(K+1)也成立，根据数学归纳法 该命题得证

19、。 证毕。 求证命题 P(n) “ 从 1开始连续 n个 奇数之和是 n的平方 ” 即公式： 1+3+5+ + (2n-1) =n2成立。 4. 递归的概念 4.3 如何表达延续不断却相似或重复的事物或过程 ? 29/57 什么是递归 ? 递归的思想源于数学的递推式和数学归纳法 。 递归是一种表达相似性对象及动作的无限性构造的方法 。 递归是一种关于抽象的表达方法 -用递归定义无限的相似事物 递归是一种算法或程序的构造技术 -自身调用自身 ， 高阶调用低阶 ， 构 造无限的计算步骤 递归 是一种典型的计算过程 -由后向前代入 ， 再由前向后计算 递归 递归基础 ：定义 、 构造和计算的起点 ，

20、 直接给出； 递归步骤 ：由前 n项或第 n项定义第 n+1项； 由低阶 f(k)且 kn， 来构造 高阶 f(n+1) -执行：由后向前代入 ， 直至代入到递归基础 ， 再由递归基础向后计算 直至计算出最终结果； 4. 递归的概念 4.4 什么是递归 ? 30/57 原始递归 -原始递归：复合 (组合 )与构造 程序与递归：组合 -抽象与构造 5. 原始递归 31/57 31 5. 原始递归 5.1 原始递归函数及其递归基础 ? 原始递归函数 是接受自然数 x或自然数的元组 (x1, xn)作为参数，并产 生自然数的一个映射，记为 f(x)或 f(x1, xn)。接受 n个参数的函数称作 n

21、元 函数 。处处有定义的函数被称作 全函数 ，未必处处有定义的函数称作 半函 数 或 部分函数 。 最基本的原始递归函数，也被称为本原函数有三个： (1)初始函数 ： 0元函数即常数无需计算；或者 常数函数 ：对于每个自然 数 n和所有的 k, 有 f(x1,x2, ,xK)=n。 (2)后继函数 ： 1 元后继函数 S，它接受一个参数并返回给出参数的 后继数 。 例如 S(1)=2, , S(x) = x+1, 其中 x为任意自然数。 (3)投影函数 ：对于所有 n1 和每个 1in 的 i， n 元投影函数 Pin，它接受 n 个参数并返回它们中的第 i 个参数， 即 Pin (x1， x

22、2， ， xn) = xi 32/57 32 (1)复合：给定原始递归函数 f(x1,.,xk)，和 k 个原始递归函数 g1,.,gk，则 f 和 g1,.,gk的复合是 函数 h, 即 h(x1,.,xm) = f(g1(x1,.,xm),.,gk(x1,.,xm) 简单而言，复合是将一系列函数作为参数代入到另一个函数中， 又被称为代入。复合是构造新函数的一种方法。复合是表达组合 的一种方法。 结构 f vs. 构件 g1, ,gk g1 ,gk的组合关系 f vs. 运算组合式 g1, ,gk g1 ,gk的指令组合关系 f vs. 基本指令 g1, ,gk 5. 原始递归 5.2 原始

23、递归函数如何构造 -组合 /复合 ? 33/57 33 (2)原始递归：给定原始递归函数 f 和 g，则新函数 h可由 f 和 g递 归的定义 ，其中 h(0,x1,.,xk) = f(x1,.,xk) h(S(n), x1,.,xk) = g(h(n,x1,.,xk)， n， x1,.,xk) 简单而言，定义新函数 h，就是要定义 h(0), h(1),h(n),。 h(0)直 接给出。 h(n+1)则由将 h(n)和 n代入 g中来构造。 原始递归是递归地构造新函数的方法，尤其是无限的相似性函数 的构造方法。 (* (* (* (* (* 1 1) 2) 3) n) S(n) 5. 原始递

24、归 5.2 原始递归函数如何构造 -组合 /复合 ? g(x1, x2) = (* x1 S(x2) h(0) = 1 h(S(n) = g(h(n), n) h(0) = 1 h(1) = g(h(0), 0) = (* 1 1) h(2) = g(h(1), 1) = (* (* 1 1) 2) h(3) = g(h(2), 2) = (* (* 1 1) 2) 3) h(S(n) = g(h(n), n) 34/57 34 原始递归函数的构造示例 已知： f(x)=x g(x1,x2,x3)=x1+x2+x3, 其中 x,x1,x2,x3均为自然数 h(0,x) = f(x)且 h(S(

25、n), x) = g(h(n,x),n,x) 该函数对任一自然数的计算过程为： h(0,x)=f(x) =x h(1,x)=h(S(0),x) = g(h(0,x),0,x) = g(f(x),0,x) = f(x) +0+ x =2x h(2,x)=h(S(1),x) = g(h(1,x),1,x)=g(g(f(x),0,x),1,x)=g(2x, 1, x)=3x+1 h(3,x)=h(S(2),x) =g(h(2,x),2,x)=g(g(h(1, x),1, x),2, x)= g(g(g(h(0,x),0,x),1,x),2,x) = = 4x+3 5. 原始递归 5.3 原始递归函数

26、构造示例 ? 35/57 35 原始递归函数的构造示例 已知： f(x)=2 g(x1,x2,x3)=x1,其中 x,x1,x2,x3均为自然数 h(0,x) = f(x)且 h(S(n), x) = g(h(n,x),n,x) 该函数对任一自然数的计算过程为： h(0,x) =f(x) =2 h(1,x) =h(S(0),x) = g(h(0,x),0,x) = g(f(x),0,x) = f(x) =2 h(2,x)=h(S(1),x) = g(h(1,x),1,x)=g(g(f(x),0,x),1,x)=g(2, 1, x)=2 h(3,x)=h(S(2),x) =g(h(2,x),2,

27、x)=g(g(h(1, x),1, x),2, x) =g(g(g(h(0,x),0,x),1,x),2,x) = = 2 5. 原始递归 5.3 原始递归函数构造示例 ? 36/57 递归与迭代 -两种不同的递归函数 -递归与迭代 程序与递归：组合 -抽象与构造 6. 递归与迭代 37/57 37 6. 递归与迭代 6.1 两种不同的递归函数 ? 递归和递推：比较下面两个示例 Fibonacci数列 ， 无穷数列 1， 1， 2， 3， 5， 8， 13， 21， 34， 55， ， 称为 Fibonacci数列 。 它可以递归地定义为： F(0)=1; F(1)=1; F(2)=F(1)+

28、F(0)=2; F(3)=F(2)+F(1)= 3; F(4)=F(3)+F(2)= 3+2=5; 1 1 0 )2()1( 1 1 )( n n n nFnF nF 递归定义 递推计算 /迭代计算 /迭代执行 定义是递归的 , 但执行可以是递归的也可是迭代的 38/57 38 递归和递推：比较下面两个示例 阿克曼递归函数 -双递归函数 阿克曼给出了一个不是原始递归的可计算的全函数。表述如下： 1, 2 0 )1),1(),( 2)0,( 1),0( 2)0,1( mn n m mmnAAmnA nnA mA A 函数本身是递归的， 函数的变量也是递归的 m=0时， A(n,0)=n+2； m

29、=1时， A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和 A(1,1)=2故 A(n,1)=2*n m=2时， A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和 A(1,2)=A(A(0,2),1)=A(1,1)=2， 故 A(n,2)= 2n。 m=3时，类似的可以推出 n2222 n 2 222 递归定义 递归计算 /递归执行 6. 递归与迭代 6.1 两种不同的递归函数 ? 由后向前代入，再由前向后计算 39/57 39 递归和递推：比较下面两个示例 阿克曼递归函数 -双递归函数 -另一种形式 0, 0 0 )1,(,1( )1),1( 1 ),( n

30、m n m nmAmA mA n nmA 若 若 若 A(1,2) = A(0,A(1,1) = A(0, A(0,A(1,0) = A(0, A(0,A(0,1)=A(0,A(0,2)=A(0,3)=4 。 A(1,3) =A(0, A(1,2)=A(0. )=A(0,4)=4+1=5。 A(1,n) =A(0, A(1,n-1)=A(0. )=A(0,n+1)=n+2。 A(2,1) = A(1， A(2， 0) = A(1， A(1， 1) =A(1， A(0， A(1， 0) = A(1， A(0， A(0， 1) = A(1， A(0， 2) = A(1， 3) =A(0， A(1，

31、 2) = A(0， A(0， A(1， 1) = A(0， A(0， A(0， A(1， 0) = A(0， A(0， A(0， A(0,1) = A(0， A(0， A(0， 2) = A(0， A(0， 3) = A(0， 4) = 5。 6. 递归与迭代 6.1 两种不同的递归函数 ? 40/57 40 迭代 (递推 )：可以由前向后依次计算或直接计算 递归：可以由前向后依次计算或直接计算；但有些，只能由 后向前代入，然后再由前向后计算。 递归包含了递推，但递推不能覆盖递归。 递归和迭代 (递推 ) 6. 递归与迭代 6.2 递归和迭代有什么差别 ? 41/57 运用递归与迭代 -用递

32、归方法进行定义 -用递归方法和迭代方法构造程序 程序与递归：组合 -抽象与构造 7. 运用递归与迭代 42/57 42 7. 运用递归和迭代 7.1 运用递归进行无限对象的定义 ? 示例：算术表达式的递归定义 运用递归定义无限自相似性对象 首先给出递归基础的定义： (1)任何一个常数 C是一个算术表达式； (2)任何一个变量 V是一个算术表达式； 再给出递归步骤： (3)如 F、 G是算术表达式，则下列运算： F+G， F-G， F*G， F/G是算术表达式； (4)如 F是表达式，则 (F)亦是算术表达式。 (5)括号内表达式优先计算，“ *”与“ /”运算优先于“ +”与“ -”运算。 (

33、6)算术表达式仅限于以上形式。 ( (100 + (X + Y) * (Z-Y) + Z) ) 43/57 43 示例： “ 某人祖先 ” 的递归定义 (1)某人的双亲是他的祖先（递归基础）。 (2)某人 祖先 的双亲同样是某人的 祖先 （递归步骤）。 7. 运用递归和迭代 7.1 运用递归进行无限对象的定义 ? 运用递归定义无限自相似性对象 44/57 44 示例：简单命题逻辑的形式化递归定义 (1)一个命题是其值为真或假的一个判断语句（递归基础）。 (2)如果 X是一个命题， Y也是一个命题，则 X and Y， X or Y, Not X也是一 个命题。（递归步骤）。 (3)如果 X是一

34、个命题，则 (X)也是一个命题，括号内的命题运算优先。 (4)命题由以上方式构造。 7. 运用递归和迭代 7.1 运用递归进行无限对象的定义 ? 运用递归定义无限自相似性对象 ( (M or (X and Y) and (Y or K) and Z) ) 45/57 45 示例：树的形式化递归定义 树是包含若干个元素的有穷集合 ， 每个元素称为结点 。 其中： (1)有且仅有一个特定的称为根的结点； (递归基础 ) (2)除根结点外的其余结点可被分为 k个互不相交的集合 T1, T2, ,Tk(k0)， 其中每一个集合 Ti本身也是一棵树，被称其为根的子树。 (递归步骤 ) 7. 运用递归和迭

35、代 7.1 运用递归进行无限对象的定义 ? 运用递归定义无限自相似性对象 46/57 46 示例：求 n!的算法或程序 时当 时当 1 1 1.)1( 1! n n nnn 时当 时当 1 1 )!1( 1 ! n n nn n 7. 运用递归和迭代 7.2 运用递归进行程序构造 ? 运用递归进行程序构造：具有无限的自相似性步骤的表达，自身 调用自身，高阶调用递阶 47/57 47 时当 时当 1 1 )!1( 1 ! n n nn n (define (fact n) ( cond ( n 1) (* n fact(n-1) ) 7. 运用递归和迭代 7.2 运用递归进行程序构造 ? 示例：

36、求 n!的算法或程序 -用递归方法构造 运用递归进行程序构造：具有无限的自相似性步骤的表达，自身 调用自身，高阶调用递阶 48/57 48 (define (f n) ( cond ( n 1) (expression n fact(n-1) ) (define (expression n m) (* (/ n 2) m) (define (expression n m) (+ n m) 时当 时当 1 1 )1(2/ 1)( n n nfnnf 时当 时当 1 1 )1( 1)( n n nfnnf 这样定义 或者这样定义 7. 运用递归和迭代 7.2 运用递归进行程序构造 ? 运用递归进行

37、程序构造：具有无限的自相似性步骤的表达，自身 调用自身，高阶调用递阶 49/57 49 7. 运用递归和迭代 7.3 递归程序的执行过程 ? 运用递归进行程序构造：具有无限的自相似性步骤的表达，自身 调用自身，高阶调用递阶 50/57 50 时当 时当 1 1 1.)1( 1! n n nnn (define (fact n) (fact-iter 1 1 n) (define (fact-iter product counter max-count) ( cond ( counter max-count) product) ( counter max-count) product) ( n

38、1) (+ (fib (- n 1) (fib (- n 2) ) 1 1 0 )2()1( 1 1 )( n n n nFnF nF 示例：求 Fibonacci数列的算法或程序 -递归 7. 运用递归和迭代 7.6 递归与迭代的比较 ? 递归定义 递归程序 递归程序的执行过程 53/57 53 (define (fib n) ( fib-iter 1 0 n) ) (define (fib-iter a b count) ( cond (= count 0) b) ( count 0) ( fib-iter (+ a b) a (- count 1) ) 1 1 0 )2()1( 1 1

39、)( n n n nFnF nF 示例：求 Fibonacci数列的算法或程序 -迭代 7. 运用递归和迭代 7.6 递归与迭代的比较 ? 递归定义 迭代程序 迭代程序的执行过程 54/57 54 递归是计算技术的典型特征，是以有限的表达方式来表达无限对象实例或无 限计算步骤的一种经典的计算思维 递归覆盖了重复、迭代和递归，递归是最典型的构造手段 递归函数是可计算函数的精确的数学描述 -计算理论的重要研究内容； (后面将介绍的 )图灵机本质上也是递归：图灵可计算函数与递归函数等价， 凡可计算的函数都是一般递归函数 -丘奇 -图灵命题 -计算理论的重要研究内容； 关于递归的进一步学习 7. 运用递归和迭代 7.7 递归还有什么 ? 55/57 什么是程序 ? 程序的本质是什么 ? 计算系统的构造 程序 -对基本动作的组合 计算系统 -执行程序的系统 程序本质 -组合、抽象、构造与执行 实例层面：运算组合式 概念层面：计算系统与程序 程序构造的基本方法：递归与迭代 组合 /抽象 递归函数 递归定义、递归算法、递归计算 本讲小结 2013-2014 Questions & Discussion? 第 3讲 程序与递归：组合 -抽象与构造