第第6讲讲 程序与递归：组合程序与递归：组合-抽象与构造抽象与构造-程序是实现系统复杂功能的一种重要手段程序是实现系统复杂功能的一种重要手段-程序的本质是组合、抽象与构造程序的本质是组合、抽象与构造-构造的基本手段是递归，一种表达相似性对象及动作构造的基本手段是递归，一种表达相似性对象及动作的无限性构造的方法的无限性构造的方法2/57程序与递归：组合程序与递归：组合-抽象与构造抽象与构造1. 程序的作用和本质程序的作用和本质?程序的作用和本质程序的作用和本质-计算系统与程序计算系统与程序-程序：组合、抽象与构造程序：组合、抽象与构造3/57首先，设计并实现系统可以执行的基本动作首先，设计并实现系统可以执行的基本动作(可实现的可实现的)，例如，例如“与与”动作动作“或或”动作动作“非非”动作动作“异或异或”动作动作那么，复杂的动作呢？那么，复杂的动作呢？系统需要提供复杂的动作系统需要提供复杂的动作复杂的动作千变万化复杂的动作千变万化复杂的动作随使用者复杂的动作随使用者使用目的的不同使用目的的不同而变化而变化复杂的动作是通过对基本动作进行各种组合来实现的复杂的动作是通过对基本动作进行各种组合来实现的1. 程序的作用和本质程序的作用和本质1.1 怎样设计并实现一个计算系统怎样设计并实现一个计算系统?如何设计实现一个基本计算系统？如何设计实现一个基本计算系统？已知的基本事实是已知的基本事实是:“加减乘除运算都可转换为加法运算来实现加减乘除运算都可转换为加法运算来实现”“加法运算又可以转换为逻辑运算来实现加法运算又可以转换为逻辑运算来实现”“基本的逻辑运算与、或、非、异或等可通基本的逻辑运算与、或、非、异或等可通过门电路予以实现过门电路予以实现” 则基本计算系统可以如下实现则基本计算系统可以如下实现 4/57指令指令：控制基本动作执行的命令：控制基本动作执行的命令“与与”动动作作“或或”动作动作 “非非”动作动作ANDOR NOT系统系统(A AND B) AND C) OR (NOT C)复杂动作复杂动作拆解开拆解开X= A AND B X= X AND CY= NOT C X= X OR Y程序程序:由基本动作指令构造的，由基本动作指令构造的，若干指令的一个组合或一个执行若干指令的一个组合或一个执行序列，用以实现复杂动作序列，用以实现复杂动作如何设计实现一个基本计算系统？如何设计实现一个基本计算系统？1.程序的作用和本质程序的作用和本质1.2 什么是程序什么是程序?5/57指令指令：控制基本动作执行的命令：控制基本动作执行的命令“与与”动动作作“或或”动作动作 “非非”动作动作ANDOR NOT系统系统(A AND B) AND C) OR (NOT C)复杂动作复杂动作程序执程序执行机构行机构自动解释程序自动解释程序中的各种组合中的各种组合, 并按次序调用并按次序调用指令指令(基本动基本动作作)予以执行予以执行程序程序:由基本动作指令构造的，由基本动作指令构造的，若干指令的一个组合或一个执行若干指令的一个组合或一个执行序列，用以实现复杂动作序列，用以实现复杂动作如何设计实现一个基本的计算系统？如何设计实现一个基本的计算系统？1.程序的作用和本质程序的作用和本质1.3 程序能否自动执行程序能否自动执行?6/57基本动作基本动作 对基本动作的对基本动作的 抽象与控制抽象与控制“与与”动作动作 AND “或或”动作动作 OR“非非”动作动作 NOT复杂动作复杂动作 = 基本动作的各种方式的组合基本动作的各种方式的组合(Ai XOR Bi) XOR Ci(Ai XOR Bi) AND Ci) OR (Ai AND Bi) 解释这种组合解释这种组合, 并并按次序调用基本动按次序调用基本动作予以执行作予以执行程序程序执行执行机构机构程序程序指令指令计算系统计算系统 = 基本动作 + 指令 + 程序执行机构指令指令 = 对可执行基本动作的抽象，即控制基本动作执行的命令程序程序 = 基本动作指令的一个组合或执行序列, 用以实现复杂的动作程序执行机构程序执行机构 = 负责解释程序即解释指令之间组合，并按次序调用指令即调用基本动作执行的机构基基本本动动作作1.程序的作用和本质程序的作用和本质1.4 计算系统与程序计算系统与程序?7/57基本动作基本动作 对基本动作的对基本动作的 抽象与控制抽象与控制“加加”动作动作 +“减减”动作动作 -“乘乘”动作动作 x“除除”动作动作 复杂动作复杂动作 = 基本动作的各种方式的组合基本动作的各种方式的组合(V1 + V2) x (V3 V4) V5(V1 (V2 x (V3 + V4) - ( V5 x V6) 解释这种组合解释这种组合, 并并按次序调用基本动按次序调用基本动作予以执行作予以执行程序程序程序程序执行执行机构机构指指令令一种较高抽象层次的一种较高抽象层次的系统系统抽象抽象抽象抽象：将经常使将经常使用的、可用的、可由低层次由低层次系统实现系统实现的一些复的一些复杂动作，杂动作，进行进行命命名名，以作，以作为高层次为高层次系统的指系统的指令被使用令被使用一种较低抽象层一种较低抽象层次的次的系统系统1.程序的作用和本质程序的作用和本质1.5 程序：组合程序：组合-抽象抽象-构造构造?8/57程序构造示例程序构造示例(I)-运算组合式的表达运算组合式的表达-组合、抽象与构造组合、抽象与构造-命名计算对象命名计算对象和和构造中使用名字构造中使用名字及及计算中以计算对象替换名字计算中以计算对象替换名字程序与递归：组合程序与递归：组合-抽象与构造抽象与构造2. 程序构造示例程序构造示例(I)9/572. 程序构造示例程序构造示例(I)2.1 运算组合式运算组合式?(100 + 205) 由数值，到基本运算组合式由数值，到基本运算组合式 中缀表示法中缀表示法, 用运算符用运算符(即前述的指令即前述的指令)将两个数值组合起来，运算符在中间将两个数值组合起来，运算符在中间(+ 100 205) 100205实际的数值实际的数值前缀表示法前缀表示法, 用运算符用运算符(即前述的指令即前述的指令)将两个数值组合起来，运算符在前面将两个数值组合起来，运算符在前面将运算符表示的操作应用于后面的一组数值上，求出结果将运算符表示的操作应用于后面的一组数值上，求出结果(+ 100 205 300 400 51 304) 一个运算符可以表示连加，一个运算符可以表示连加，连减等情况，连减等情况，10/57(+ 100 205) (- 200 50) (* 200 5) (* 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 ) 4322. 程序构造示例程序构造示例(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 如何用名字简化运算组合式的构造如何用名字简化运算组合式的构造?-抽象抽象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)-组合、抽象与构造组合、抽象与构造-命名新运算符命名新运算符和和构造中使用新运构造中使用新运算符算符及及执行中以过程替换新运算符执行中以过程替换新运算符-带有条件的运算组合式带有条件的运算组合式程序与递归：组合程序与递归：组合-抽象与构造抽象与构造3. 程序构造示例程序构造示例(II)15/57(define (square x) (* x x) 名字的定义：定义名字名字的定义：定义名字square为一个为一个新的运算，即过程或称函数新的运算，即过程或称函数另一种类型的名字：运算符型的名字另一种类型的名字：运算符型的名字名字的使用名字的使用注意：不同类型的对象可以有不同的定义方法。这里统一用注意：不同类型的对象可以有不同的定义方法。这里统一用define来表示，在具体的程序设计语言中是用不同的方法来定义的来表示，在具体的程序设计语言中是用不同的方法来定义的新运算符，即过程名或函数名新运算符，即过程名或函数名形式参数，形式参数，使用时将被实使用时将被实际参数所替代际参数所替代过程体，用于表示新运算符的具体计过程体，用于表示新运算符的具体计算规则，其为关于形式参数算规则，其为关于形式参数x的一种的一种计算组合。计算组合。(square 3)(square 6) x2命名新运算符命名新运算符和和构造中使用新运算符构造中使用新运算符及及执行中以过程替换新运算符执行中以过程替换新运算符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(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) (* 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) (* (* (+ 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. 程序构造示例程序构造示例(II) 3.4 有条件的运算如何表达有条件的运算如何表达?带有条件的运算组合式带有条件的运算组合式21/57u问题问题1：用前缀表示法书写下述表达式：用前缀表示法书写下述表达式 10 + 4 + (8- (12 - (6 + 4 5)3*(6-2)(12-7)u问题问题2：请定义一个过程，求某一数值的立方：请定义一个过程，求某一数值的立方a3u问题问题3：进一步以问题：进一步以问题2定义的过程，再定义一个定义的过程，再定义一个过程，求某两个数值的立方和。过程，求某两个数值的立方和。 进一步求进一步求 ，并模拟给出计算过程。，并模拟给出计算过程。a3+b353+833. 程序构造示例程序构造示例(II) 3.5 你能表达与构造程序吗你能表达与构造程序吗?22/57(cond ( ) ( ). ( ) ) (define (f x) (cond ( x 0) (- (Square x) x) (= x 0) 0) (=1时时 等比数列递推公式等比数列递推公式a0=5an=an-1 20 当当n=1时时 第第1项项(或前或前K项项)的值是已知的的值是已知的递推基础递推基础；由第由第n项或前项或前n项计算第项计算第n+1项项递推规则递推规则/递推步骤递推步骤；由前向后，可依次计算每一项由前向后，可依次计算每一项等差数列的产生等差数列的产生a0=5a1=a0+3 = 8a2=a1+3 = 11a3=a2+3 = 14a4=a3+3 = 17 28/5728数学中的数学归纳法数学中的数学归纳法u数数学学归归纳纳法法是是一一种种用用于于证证明明与与自自然然数数有有关关的的命命题题正正确确性性的的证证明明方方法法，该该方方法能用有限的步骤解决无穷对象的论证问题。法能用有限的步骤解决无穷对象的论证问题。u由归纳基础和归纳步骤构成：l假定对一切正整数假定对一切正整数n, 有一个命题有一个命题P(n),若以下证明成立若以下证明成立, 则则P(n)为真。为真。 l (1)归纳基础归纳基础: 证明证明P(1)为真；为真； l (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)也成立也成立，根据数学归纳法根据数学归纳法该命题得证。该命题得证。 证毕。证毕。求证命题求证命题P(n) “从从1开始连续开始连续n个个奇数之和是奇数之和是n的平方的平方” 即公式：即公式：1+3+5+ (2n-1) =n2成立。成立。4. 递归的概念递归的概念4.3 如何表达延续不断却相似或重复的事物或过程如何表达延续不断却相似或重复的事物或过程?29/57什么是递归?递归的思想源于数学的递推式和数学归纳法。递归是一种表达相似性对象及动作的无限性构造的方法。u递归是一种关于抽象的表达方法-用递归定义无限的相似事物用递归定义无限的相似事物u递归是一种算法或程序的构造技术-自自身身调调用用自自身身，高高阶阶调调用用低低阶阶，构构造无限的计算步骤造无限的计算步骤u递归是一种典型的计算过程-由后向前代入，再由前向后计算由后向前代入，再由前向后计算递归递归n递归基础递归基础：定义、构造和计算的起点，直接给出；n递递归归步步骤骤：由前n项或第n项定义第n+1项；由低阶f(k)且kn，来构造高阶f(n+1)-执行：由后向前代入，直至代入到递归基础，再由递归基础向后计算直至计算出最终结果；4. 递归的概念递归的概念4.4 什么是递归什么是递归?30/57原始递归原始递归-原始递归：复合原始递归：复合(组合组合)与构造与构造程序与递归：组合程序与递归：组合-抽象与构造抽象与构造5. 原始递归原始递归31/57315. 原始递归原始递归5.1 原始递归函数及其递归基础原始递归函数及其递归基础?原始递归函数原始递归函数是接受自然数是接受自然数x或自然数的元组或自然数的元组(x1,xn)作为参数，并产作为参数，并产生自然数的一个映射，记为生自然数的一个映射，记为f(x)或或f(x1,xn)。接受。接受n个参数的函数称作个参数的函数称作n元元函数函数。处处有定义的函数被称作。处处有定义的函数被称作全函数全函数，未必处处有定义的函数称作，未必处处有定义的函数称作半函半函数数或或部分函数部分函数。 最基本的原始递归函数，也被称为本原函数有三个：最基本的原始递归函数，也被称为本原函数有三个：(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，x2，xn) = xi 32/5732(1)复合：给定原始递归函数复合：给定原始递归函数 f(x1,.,xk)，和，和 k 个原始递归函数个原始递归函数 g1,.,gk，则，则f 和和 g1,.,gk的复合是的复合是 函数函数h, 即即h(x1,.,xm) = f(g1(x1,.,xm),.,gk(x1,.,xm)简单而言，复合是将一系列函数作为参数代入到另一个函数中，简单而言，复合是将一系列函数作为参数代入到另一个函数中，又被称为代入。复合是构造新函数的一种方法。复合是表达组合又被称为代入。复合是构造新函数的一种方法。复合是表达组合的一种方法。的一种方法。结构结构f vs. 构件构件g1,gkg1,gk的组合关系的组合关系f vs. 运算组合式运算组合式g1,gkg1,gk的指令组合关系的指令组合关系f vs. 基本指令基本指令g1,gk5. 原始递归原始递归5.2 原始递归函数如何构造原始递归函数如何构造-组合组合/复合复合?33/5733(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. 原始递归原始递归5.2 原始递归函数如何构造原始递归函数如何构造-组合组合/复合复合?g(x1, x2) = (* x1 S(x2)h(0) = 1h(S(n) = g(h(n), n)h(0) = 1h(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/5734原始递归函数的构造示例原始递归函数的构造示例p已知：已知：f(x)=x g(x1,x2,x3)=x1+x2+x3, 其中其中x,x1,x2,x3均为自然数均为自然数h(0,x) = f(x)且且 h(S(n), x) = g(h(n,x),n,x)该函数对任一自然数的计算过程为：该函数对任一自然数的计算过程为： h(0,x)=f(x) =xh(1,x)=h(S(0),x) = g(h(0,x),0,x) = g(f(x),0,x) = f(x) +0+ x =2xh(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+1h(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 原始递归函数构造示例原始递归函数构造示例?35/5735原始递归函数的构造示例原始递归函数的构造示例p已知：已知：f(x)=2g(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) =2h(1,x) =h(S(0),x) = g(h(0,x),0,x) = g(f(x),0,x) = f(x) =2h(2,x)=h(S(1),x) = g(h(1,x),1,x)=g(g(f(x),0,x),1,x)=g(2, 1, x)=2h(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) = = 2 5. 原始递归原始递归5.3 原始递归函数构造示例原始递归函数构造示例?36/57递归与迭代递归与迭代-两种不同的递归函数两种不同的递归函数-递归与迭代递归与迭代程序与递归：组合程序与递归：组合-抽象与构造抽象与构造6. 递归与迭代递归与迭代37/57376. 递归与迭代递归与迭代6.1 两种不同的递归函数两种不同的递归函数?递归和递推：比较下面两个示例递归和递推：比较下面两个示例p Fibonacci数数列列，无无穷穷数数列列1，1，2，3，5，8，13，21，34，55，称称为为Fibonacci数列。它可以递归地定义为：数列。它可以递归地定义为： F(0)=1; F(1)=1; F(2)=F(1)+F(0)=2; F(3)=F(2)+F(1)= 3; F(4)=F(3)+F(2)= 3+2=5; 递归定义递归定义递推计算递推计算/迭代计算迭代计算/迭代执行迭代执行定义是递归的定义是递归的, 但执行可以是递归的也可是迭代的但执行可以是递归的也可是迭代的38/5738递归和递推：比较下面两个示例递归和递推：比较下面两个示例p阿克曼递归函数阿克曼递归函数-双递归函数双递归函数p阿克曼给出了一个不是原始递归的可计算的全函数。表述如下：阿克曼给出了一个不是原始递归的可计算的全函数。表述如下： 函数本身是递归的，函数本身是递归的，函数的变量也是递归的函数的变量也是递归的 m=0时，A(n,0)=n+2；m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nm=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时，类似的可以推出 递归定义递归定义递归计算递归计算/递归执行递归执行6. 递归与迭代递归与迭代6.1 两种不同的递归函数两种不同的递归函数?由后向前代入，再由前向后计算由后向前代入，再由前向后计算39/5739递归和递推：比较下面两个示例递归和递推：比较下面两个示例p阿克曼递归函数阿克曼递归函数-双递归函数双递归函数-另一种形式另一种形式 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，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/5740u迭代迭代(递推递推)：可以由前向后依次计算或直接计算：可以由前向后依次计算或直接计算u递归：可以由前向后依次计算或直接计算；但有些，只能由递归：可以由前向后依次计算或直接计算；但有些，只能由后向前代入，然后再由前向后计算。后向前代入，然后再由前向后计算。u递归包含了递推，但递推不能覆盖递归。递归包含了递推，但递推不能覆盖递归。 递归和迭代递归和迭代(递推递推)6. 递归与迭代递归与迭代6.2 递归和迭代有什么差别递归和迭代有什么差别?41/57运用递归与迭代运用递归与迭代-用递归方法进行定义用递归方法进行定义-用递归方法和迭代方法构造程序用递归方法和迭代方法构造程序程序与递归：组合程序与递归：组合-抽象与构造抽象与构造7. 运用递归与迭代运用递归与迭代42/57427. 运用递归和迭代运用递归和迭代7.1 运用递归进行无限对象的定义运用递归进行无限对象的定义?u示例：算术表达式的递归定义示例：算术表达式的递归定义运用递归定义无限自相似性对象运用递归定义无限自相似性对象首先给出递归基础的定义：首先给出递归基础的定义：(1)任何一个常数任何一个常数C是一个算术表达式；是一个算术表达式；(2)任何一个变量任何一个变量V是一个算术表达式；是一个算术表达式；再给出递归步骤：再给出递归步骤：(3)如如F、G是算术表达式，则下列运算：是算术表达式，则下列运算：F+G，F-G，F*G，F/G是算术表达式；是算术表达式；(4)如如F是表达式，则是表达式，则(F)亦是算术表达式。亦是算术表达式。(5)括号内表达式优先计算，括号内表达式优先计算，“*”与与“/”运算优先于运算优先于“+”与与“-”运算。运算。(6)算术表达式仅限于以上形式。算术表达式仅限于以上形式。( (100 + (X + Y) * (Z-Y) + Z) )43/5743u示例：示例：“某人祖先某人祖先”的递归定义的递归定义 (1)某人的双亲是他的祖先（递归基础）。某人的双亲是他的祖先（递归基础）。(2)某人某人祖先祖先的双亲同样是某人的的双亲同样是某人的祖先祖先（递归步骤）。（递归步骤）。7. 运用递归和迭代运用递归和迭代7.1 运用递归进行无限对象的定义运用递归进行无限对象的定义?运用递归定义无限自相似性对象运用递归定义无限自相似性对象44/5744u示例：简单命题逻辑的形式化递归定义示例：简单命题逻辑的形式化递归定义 (1)一个命题是其值为真或假的一个判断语句（递归基础）。一个命题是其值为真或假的一个判断语句（递归基础）。(2)如果如果X是一个命题，是一个命题，Y也是一个命题，则也是一个命题，则X and Y，X or Y, Not X也是一也是一个命题。（递归步骤）。个命题。（递归步骤）。(3)如果如果X是一个命题，则是一个命题，则(X)也是一个命题，括号内的命题运算优先。也是一个命题，括号内的命题运算优先。(4)命题由以上方式构造。命题由以上方式构造。7. 运用递归和迭代运用递归和迭代7.1 运用递归进行无限对象的定义运用递归进行无限对象的定义?运用递归定义无限自相似性对象运用递归定义无限自相似性对象( (M or (X and Y) and (Y or K) and Z) )45/5745u示例：树的形式化递归定义示例：树的形式化递归定义 树是包含若干个元素的有穷集合，每个元素称为结点。其中：树是包含若干个元素的有穷集合，每个元素称为结点。其中：(1)有且仅有一个特定的称为根的结点；有且仅有一个特定的称为根的结点；(递归基础递归基础) (2)除根结点外的其余结点可被分为除根结点外的其余结点可被分为k个互不相交的集合个互不相交的集合T1, T2,Tk(k 0)，其中每一个集合其中每一个集合Ti本身也是一棵树，被称其为根的子树。本身也是一棵树，被称其为根的子树。(递归步骤递归步骤) 7. 运用递归和迭代运用递归和迭代7.1 运用递归进行无限对象的定义运用递归进行无限对象的定义?运用递归定义无限自相似性对象运用递归定义无限自相似性对象46/5746u示例：求示例：求n!的算法或程序的算法或程序 7. 运用递归和迭代运用递归和迭代7.2 运用递归进行程序构造运用递归进行程序构造?运用递归进行程序构造：具有无限的自相似性步骤的表达，自身运用递归进行程序构造：具有无限的自相似性步骤的表达，自身调用自身，高阶调用递阶调用自身，高阶调用递阶47/5747(define (fact n) ( cond ( n 1) (* n fact(n-1) )7. 运用递归和迭代运用递归和迭代7.2 运用递归进行程序构造运用递归进行程序构造?u示例：求示例：求n!的算法或程序的算法或程序 -用递归方法构造用递归方法构造运用递归进行程序构造：具有无限的自相似性步骤的表达，自身运用递归进行程序构造：具有无限的自相似性步骤的表达，自身调用自身，高阶调用递阶调用自身，高阶调用递阶48/5748(define (f n) ( cond ( n 1) (expression n fact(n-1) )(define (expression n m) (* (/ n 2) m)(define (expression n m) (+ n m)这样定义这样定义或者这样定义或者这样定义7. 运用递归和迭代运用递归和迭代7.2 运用递归进行程序构造运用递归进行程序构造?运用递归进行程序构造：具有无限的自相似性步骤的表达，自身运用递归进行程序构造：具有无限的自相似性步骤的表达，自身调用自身，高阶调用递阶调用自身，高阶调用递阶49/57497. 运用递归和迭代运用递归和迭代7.3 递归程序的执行过程递归程序的执行过程?运用递归进行程序构造：具有无限的自相似性步骤的表达，自身运用递归进行程序构造：具有无限的自相似性步骤的表达，自身调用自身，高阶调用递阶调用自身，高阶调用递阶50/5750(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 1) (+ (fib (- n 1) (fib (- n 2) )示例：求示例：求Fibonacci数列数列的算法或程序的算法或程序-递归递归7. 运用递归和迭代运用递归和迭代7.6 递归与迭代的比较递归与迭代的比较?递归定义递归定义递归程序递归程序递归程序的执行过程递归程序的执行过程53/5753(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) ) 示例：求示例：求Fibonacci数列数列的算法或程序的算法或程序-迭代迭代7. 运用递归和迭代运用递归和迭代7.6 递归与迭代的比较递归与迭代的比较?递归定义递归定义迭代程序迭代程序迭代程序的执行过程迭代程序的执行过程54/5754u递归是计算技术的典型特征，是以有限的表达方式来表达无限对象实例或无递归是计算技术的典型特征，是以有限的表达方式来表达无限对象实例或无限计算步骤的一种经典的计算思维限计算步骤的一种经典的计算思维u递归覆盖了重复、迭代和递归，递归是最典型的构造手段递归覆盖了重复、迭代和递归，递归是最典型的构造手段u递归函数是可计算函数的精确的数学描述递归函数是可计算函数的精确的数学描述-计算理论的重要研究内容；计算理论的重要研究内容；u(后面将介绍的后面将介绍的)图灵机本质上也是递归：图灵可计算函数与递归函数等价，凡图灵机本质上也是递归：图灵可计算函数与递归函数等价，凡可计算的函数都是一般递归函数可计算的函数都是一般递归函数-丘奇丘奇-图灵命题图灵命题-计算理论的重要研究内容；计算理论的重要研究内容；关于递归的进一步学习关于递归的进一步学习 7. 运用递归和迭代运用递归和迭代7.7 递归还有什么递归还有什么?55/57什么是程序什么是程序? ?程序的本质是什么程序的本质是什么? ?计算系统的构造计算系统的构造程序程序-对基本动作的组合对基本动作的组合计算系统计算系统-执行程序的系统执行程序的系统程序本质程序本质-组合、抽象、构造与执行组合、抽象、构造与执行实例层面：运算组合式实例层面：运算组合式概念层面：计算系统与程序概念层面：计算系统与程序程序构造的基本方法：递归与迭代程序构造的基本方法：递归与迭代组合组合/抽象抽象 递归函数递归函数递归定义、递归算法、递归计算递归定义、递归算法、递归计算相互关联且递进的方式展开与贯通相互关联且递进的方式展开与贯通概念概念/原理与案例相结合原理与案例相结合知识伴随思维，思维贯通知识知识伴随思维，思维贯通知识本讲小结本讲小结2013-2014Questions & Discussion?第第3讲讲 程序与递归：组合程序与递归：组合-抽象与构造抽象与构造