没有幻灯片标题

Size: px

Start display at page:

Download "没有幻灯片标题"

围禹
5 years ago
Views:

1 第 8 讲程序与递归 : 组合 - 抽象与构造 -- 程序是实现系统复杂功能的一种重要手段 -- 程序的本质是组合抽象与构造 -- 构造的基本手段是递归, 一种表达相似性对象及动作的无限性构造的方法

2 程序与递归 : 组合 - 抽象与构造 1. 程序的作用和本质? 2/57 程序的作用和本质 ---- 计算系统与程序 ---- 程序 : 组合抽象与构造

3 1. 程序的作用和本质 1.1 怎样设计并实现一个计算系统? 3/57 如何设计实现一个基本计算系统? 首先, 设计并实现系统可以执行的基本动作 ( 可实现的 ), 例如与动作或动作非动作异或动作那么, 复杂的动作呢? 系统需要提供复杂的动作复杂的动作千变万化已知的基本事实是 : 加减乘除运算都可转换为加法运算来实现加法运算又可以转换为逻辑运算来实现基本的逻辑运算与或非异或等可通过门电路予以实现则基本计算系统可以如下实现复杂的动作随使用者使用目的的不同而变化复杂的动作是通过对基本动作进行各种组合来实现的

4 1. 程序的作用和本质 1.2 什么是程序? 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 指令 : 控制基本动作执行的命令

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

6 1. 程序的作用和本质 1.4 计算系统与程序? 6/57 计算系统 = 基本动作 + 指令 + 程序执行机构指令 = 对可执行基本动作的抽象, 即控制基本动作执行的命令程序 = 基本动作指令的一个组合或执行序列, 用以实现复杂的动作程序执行机构 = 负责解释程序即解释指令之间组合, 并按次序调用指令即调用基本动作执行的机构程序复杂动作 = 基本动作的各种方式的组合 (A i XOR B i ) XOR C i ((A i XOR B i ) AND C i ) OR (A i AND B i ) 基本动作基本动作对基本动作的抽象与控制与动作 AND 或动作 OR 非动作 NOT 指令解释这种组合, 并按次序调用基本动作予以执行程序执行机构

7 1. 程序的作用和本质 1.5 程序 : 组合 - 抽象 - 构造? 7/57 抽象 : 将经常使用的可由低层次系统实现的一些复杂动作, 进行命名, 以作为高层次系统的指令被使用一种较高抽象层次的系统基本动作加动作 + 减动作 - 乘动作 x 除动作基本动作对基本动作的抽象与控制指令一种较低抽象层次的系统基本动作对基本动作的抽象与控制与动作 AND 或动作 OR 非动作 NOT 抽象指令程序复杂动作 = 基本动作的各种方式的组合程序 (A i XOR B i ) XOR C i 复杂动作 = 基本动作的各种方式的组合 (V1 + V2) x (V3 V4) V5 (V1 (V2 x (V3 + V4)) - ( V5 x V6) 解释这种组合, 并按次序调用基本动作予以执行 ((A i XOR B i ) AND C i ) OR (A i AND B i ) 解释这种组合, 并按次序调用基本动作予以执行程序执行机构程序执行机构

8 程序与递归 : 组合 - 抽象与构造 2. 程序构造示例 (I) 8/57 程序构造示例 (I) ---- 运算组合式的表达 ---- 组合抽象与构造 ---- 命名计算对象和构造中使用名字及计算中以计算对象替换名字

9 2. 程序构造示例 (I) 2.1 运算组合式? 9/57 由数值, 到基本运算组合式实际的数值 ( ) 中缀表示法, 用运算符 ( 即前述的指令 ) 将两个数值组合起来, 运算符在中间 ( ) 前缀表示法, 用运算符 ( 即前述的指令 ) 将两个数值组合起来, 运算符在前面将运算符表示的操作应用于后面的一组数值上, 求出结果 ( ) 一个运算符可以表示连加, 连减等情况,

10 2. 程序构造示例 (I) 2.1 运算组合式? 10/57 由数值, 到基本运算组合式 ( ) ( ) (* 200 5) (* ) ( ) ( ) 一起练习, 书写程序,

11 2. 程序构造示例 (I) 2.2 如何构造运算组合式 --- 组合 11/57 运算组合式的嵌套及其计算过程 ( ) (+ ( ) ( )) (* (* 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

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

13 2. 程序构造示例 (I) 2.3 如何用名字简化运算组合式的构造?-- 抽象 13/57 命名计算对象和构造中使用名字及计算中以计算对象替换名字 (define pi ) (define radius 10) (* pi (* radius radius)) (define circumference (* 2 pi radius)) (* circmference 20)

14 程序与递归 : 组合 - 抽象与构造 3. 程序构造示例 (II) 14/57 程序构造示例 (II) ---- 组合抽象与构造 ---- 命名新运算符和构造中使用新运算符及执行中以过程替换新运算符 ---- 带有条件的运算组合式

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

16 3. 程序构造示例 (II) 3.2 程序构造组合与抽象 16/57 命名新运算符和构造中使用新运算符及执行中以过程替换新运算符 (square 10) (square (+ 2 8)) (square (square 3)) (square (square (+ 2 5))) 名字的使用 (define (SumOfSquare x y) (+ (square x) (square y)) x 2 +y 2 (SumOfSquare 3 4) (+ (SumOfSquare 3 4) height)

17 3. 程序构造示例 (II) 3.2 程序构造组合与抽象 17/57 命名新运算符和构造中使用新运算符及执行中以过程替换新运算符 (define (NewProc a) (SumOfSquare (+ a 1) (* a 2))) (a+1) 2 +(a*2) 2 (NewProc 3) (NewProc (+ 3 1))

18 3. 程序构造示例 (II) 3.3 构造程序的执行求值代入与计算 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)) ( ) 89

19 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))) (+ (* (+ (+ 3 1) 1) (+ (+ 3 1) 1)) (* (* (+ 3 1) 2) (* (+ 3 1) 2))) (+ (* (+ 4 1) (+ 4 1)) (* (* 4 2) (* 4 2))) 代入阶段求值阶段 (+ (* 5 5) (* 8 8)) ( ) 89

20 3. 程序构造示例 (II) 3.4 有条件的运算如何表达? 20/57 带有条件的运算组合式 (cond ( <e 1 >) ( <e 2 >)... ( <e n >) ) (define (abs x) (cond ((> x 0) x) ((= x 0) 0) ((< x 0) (- x))))

21 3. 程序构造示例 (II) 3.5 你能表达与构造程序吗? 21/57 问题 1: 用前缀表示法书写下述表达式 (8- (12 - (6 + 45))) 3*(6-2)(12-7) 问题 2: 请定义一个过程, 求某一数值的立方 a 3 问题 3: 进一步以问题 2 定义的过程, 再定义一个过程, 求某两个数值的立方和求 a 3+ b 3, 并模拟给出计算过程进一步

22 3. 程序构造示例 (II) 3.5 你能表达与构造程序吗? 22/57 问题 4: 请定义一个过程, 计算下列函数 f ( x) 2 x x 0 2 x x if if if x x x (cond ( <e 1 >) ( <e 2 >)... ( <e n >) ) (define (f x) (cond ((> x 0) (- (Square x) x)) ((= x 0) 0) ((< x 0) (- x (Square x) )) ))

23 程序与递归 : 组合 - 抽象与构造 4. 递归的概念 23/57 递归的概念 ---- 为什么需要递归 ---- 递归能解决什么问题

24 4. 递归的概念 4.1 为什么需要递归? 递归 (Recursion) 24/57 24 (* (* (* (* (* 1 1) 2) 3) 4) n) 怎样在表达中既去掉省略号, 而又能表达近乎无限的内容从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事呢! 故事是什么呢?( 从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事呢! 故事是什么呢?( 从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事呢! 故事是什么呢?( 从前 )))

25 4. 递归的概念 4.2 什么情况需要递归? 25/57 25 递归的典型视觉形式 --- 自相似性事物的无限重复性构造

26 4. 递归的概念 4.2 什么情况需要递归? 26/57 26 递归的典型视觉形式 --- 自相似性事物的无限重复性构造

27 4. 递归的概念 4.3 如何表达延续不断却相似或重复的事物或过程? 数学中的递推式 27/57 27 一个数列的第 n 项 a n 与该数列的其他一项或多项之间存在某种对应关系, 被表达为一种公式, 称为递推式等比数列递推公式 a 0 =5 a n =a n-1 20 当 n>=1 时等差数列递推公式 a 0 =5 a n =a n 当 n>=1 时第 1 项 ( 或前 K 项 ) 的值是已知的递推基础 ; 由第 n 项或前 n 项计算第 n+1 项递推规则 / 递推步骤 ; 由前向后, 可依次计算每一项等差数列的产生 a 0 =5 a 1 =a 0 +3 = 8 a 2 =a 1 +3 = 11 a 3 =a 2 +3 = 14 a 4 =a 3 +3 = 17

28 4. 递归的概念 4.3 如何表达延续不断却相似或重复的事物或过程? 数学中的数学归纳法 28/57 28 数学归纳法是一种用于证明与自然数有关的命题正确性的证明方法, 该方法能用有限的步骤解决无穷对象的论证问题由归纳基础和归纳步骤构成 : 假定对一切正整数 n, 有一个命题 P(n), 若以下证明成立, 则 P(n) 为真 (1) 归纳基础 : 证明 P(1) 为真 ; (2) 归纳步骤 : 证明对任意的 i, 若 P(i) 为真, 则 P(i+1) 也为真求证命题 P(n) 从 1 开始连续 n 个奇数之和是 n 的平方即公式 : (2n-1) =n 2 成立证明 : (1) 归纳基础 : 当 n=1 时, 等式成立即 1=1; (2) 归纳步骤 : 设对任意 k, P(k) 成立, 即 (2K-1)=K 2. 则 P(K+1) = (2K-1) + (2(K+1)-1) = K 2 +2K+1=(K+1) 2, 则当 P(k) 成立时 P(K+1) 也成立, 根据数学归纳法该命题得证证毕

29 4. 递归的概念 4.4 什么是递归? 29/57 什么是递归? 递归的思想源于数学的递推式和数学归纳法递归是一种表达相似性对象及动作的无限性构造的方法递归是一种关于抽象的表达方法 --- 用递归定义无限的相似事物递归是一种算法或程序的构造技术 --- 自身调用自身, 高阶调用低阶, 构造无限的计算步骤递归是一种典型的计算过程 --- 由后向前代入, 再由前向后计算递归递归基础 : 定义构造和计算的起点, 直接给出 ; 递归步骤 : 由前 n 项或第 n 项定义第 n+1 项 ; 由低阶 f(k) 且 k<n, 来构造高阶 f(n+1) ---- 执行 : 由后向前代入, 直至代入到递归基础, 再由递归基础向后计算直至计算出最终结果 ;

30 程序与递归 : 组合 - 抽象与构造 5. 原始递归 30/57 原始递归 ---- 原始递归 : 复合 ( 组合 ) 与构造

31 5. 原始递归 5.1 原始递归函数及其递归基础? 31/57 31 原始递归函数是接受自然数 x 或自然数的元组 (x 1, x n ) 作为参数, 并产生自然数的一个映射, 记为 f(x) 或 f(x 1, x n ) 接受 n 个参数的函数称作 n 元函数处处有定义的函数被称作全函数, 未必处处有定义的函数称作半函数或部分函数最基本的原始递归函数, 也被称为本原函数有三个 : (1) 初始函数 :0 元函数即常数无需计算 ; 或者常数函数 : 对于每个自然数 n 和所有的 k, 有 f(x 1,x 2,,x K )=n (2) 后继函数 :1 元后继函数 S, 它接受一个参数并返回给出参数的后继数例如 S(1)=2,, S(x) = x+1, 其中 x 为任意自然数 (3) 投影函数 : 对于所有 n 1 和每个 1 i n 的 i,n 元投影函数 P in, 它接受 n 个参数并返回它们中的第 i 个参数, 即 P in (x 1,x 2,,x n ) = x i

32 5. 原始递归 5.2 原始递归函数如何构造 ---- 组合 / 复合? 32/57 32 (1) 复合 : 给定原始递归函数 f(x 1,...,x k ), 和 k 个原始递归函数 g 1,...,g k, 则 f 和 g 1,...,g k 的复合是函数 h, 即 h(x 1,...,x m ) = f(g 1 (x 1,...,x m ),...,g k (x 1,...,x m )) 简单而言, 复合是将一系列函数作为参数代入到另一个函数中, 又被称为代入复合是构造新函数的一种方法复合是表达组合的一种方法 g 1,g k 的指令组合关系 f vs. 基本指令 g 1,,g k g 1,g k 的组合关系 f vs. 运算组合式 g 1,,g k 结构 f vs. 构件 g 1,,g k

33 5. 原始递归 5.2 原始递归函数如何构造 ---- 组合 / 复合? 33/57 33 (2) 原始递归 : 给定原始递归函数 f 和 g, 则新函数 h 可由 f 和 g 递归的定义, 其中 h(0,x 1,...,x k ) = f(x 1,...,x k ) h(s(n), x 1,...,x k ) = g(h(n,x 1,...,x k ),n,x 1,...,x k ) 简单而言, 定义新函数 h, 就是要定义 h(0), h(1),,h(n), h(0) 直接给出 h(n+1) 则由将 h(n) 和 n 代入 g 中来构造原始递归是递归地构造新函数的方法, 尤其是无限的相似性函数的构造方法 (* (* (* (* (* 1 1) 2) 3) n) S(n)) g(x 1, x 2 ) = (* x 1 S(x 2 )) 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 5. 原始递归 5.3 原始递归函数构造示例? 34/57 34 原始递归函数的构造示例已知 : f(x)=x g(x 1,x 2,x 3 )=x 1 +x 2 +x 3, 其中 x,x 1,x 2,x 3 均为自然数 h(0,x) = f(x) 且 h(s(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

35 5. 原始递归 5.3 原始递归函数构造示例? 原始递归函数的构造示例已知 : f(x)=2 g(x 1,x 2,x 3 )=x 1, 其中 x,x 1,x 2,x 3 均为自然数 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 35/57 35 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) = = 2

36 程序与递归 : 组合 - 抽象与构造 6. 递归与迭代 36/57 递归与迭代 ---- 两种不同的递归函数 ---- 递归与迭代

37 6. 递归与迭代 6.1 两种不同的递归函数? 37/57 37 递归和递推 : 比较下面两个示例 Fibonacci 数列, 无穷数列 1,1,2,3,5,8,13,21,34,55,, 称为 Fibonacci 数列它可以递归地定义为 : F ( n) 1 1 F( n 1) F( n 2) n 0 n 1 n 1 递归定义 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 n 6. 递归与迭代 6.1 两种不同的递归函数? 38/57 38 递归和递推 : 比较下面两个示例阿克曼递归函数 --- 双递归函数阿克曼给出了一个不是原始递归的可计算的全函数表述如下 : A(1,0) 2 A(0, m) 1 A( n,0) n 2 m 0 n 2 递归定义函数本身是递归的, 函数的变量也是递归的 A( n, m) A( A( n 1, m), m 1) n, m 1 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*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)= 2 n m=3 时, 类似的可以推出 n 递归计算 / 递归执行由后向前代入, 再由前向后计算

39 6. 递归与迭代 6.1 两种不同的递归函数? 递归和递推 : 比较下面两个示例阿克曼递归函数 --- 双递归函数 --- 另一种形式 n 1 若 m 0 A( m, n) A(( m 1),1) 若 n 0 A( m 1, A( m, n 1)) 若 m, n 0 39/57 39 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

40 6. 递归与迭代 6.2 递归和迭代有什么差别? 递归和迭代 ( 递推 ) 迭代 ( 递推 ): 可以由前向后依次计算或直接计算 40/57 40 递归 : 可以由前向后依次计算或直接计算 ; 但有些, 只能由后向前代入, 然后再由前向后计算递归包含了递推, 但递推不能覆盖递归

41 程序与递归 : 组合 - 抽象与构造 7. 运用递归与迭代 41/57 运用递归与迭代 ---- 用递归方法进行定义 ---- 用递归方法和迭代方法构造程序

42 7. 运用递归和迭代 7.1 运用递归进行无限对象的定义? 运用递归定义无限自相似性对象示例 : 算术表达式的递归定义 42/57 42 首先给出递归基础的定义 : (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 7. 运用递归和迭代 7.1 运用递归进行无限对象的定义? 运用递归定义无限自相似性对象示例 : 某人祖先的递归定义 43/57 43 (1) 某人的双亲是他的祖先 ( 递归基础 ) (2) 某人祖先的双亲同样是某人的祖先 ( 递归步骤 )

44 7. 运用递归和迭代 7.1 运用递归进行无限对象的定义? 运用递归定义无限自相似性对象示例 : 简单命题逻辑的形式化递归定义 44/57 44 (1) 一个命题是其值为真或假的一个判断语句 ( 递归基础 ) (2) 如果 X 是一个命题,Y 也是一个命题, 则 X and Y,X or Y, Not X 也是一个命题 ( 递归步骤 ) (3) 如果 X 是一个命题, 则 (X) 也是一个命题, 括号内的命题运算优先 (4) 命题由以上方式构造 ( (((M or (X and Y)) and (Y or K)) and Z) )

45 7. 运用递归和迭代 7.1 运用递归进行无限对象的定义? 运用递归定义无限自相似性对象示例 : 树的形式化递归定义 45/57 45 树是包含若干个元素的有穷集合, 每个元素称为结点其中 : (1) 有且仅有一个特定的称为根的结点 ;( 递归基础 ) (2) 除根结点外的其余结点可被分为 k 个互不相交的集合 T 1, T 2,,T k (k0), 其中每一个集合 T i 本身也是一棵树, 被称其为根的子树 ( 递归步骤 )

46 46/57 46 示例 : 求 n! 的算法或程序时当时当 ) ( 1! n n n n n 时当时当 1 1 1)! ( 1! n n n n n 7. 运用递归和迭代 7.2 运用递归进行程序构造? 运用递归进行程序构造 : 具有无限的自相似性步骤的表达, 自身调用自身, 高阶调用递阶

47 7. 运用递归和迭代 7.2 运用递归进行程序构造? 47/57 47 运用递归进行程序构造 : 具有无限的自相似性步骤的表达, 自身调用自身, 高阶调用递阶示例 : 求 n! 的算法或程序 -- 用递归方法构造 n! n 1 ( n 1)! 当 n 当 n 1时 1时 (define (fact n) ( cond ((<= n 1) 1) ((> n 1) (* n fact(n-1))) ))

48 7. 运用递归和迭代 7.2 运用递归进行程序构造? 48/57 48 运用递归进行程序构造 : 具有无限的自相似性步骤的表达, 自身调用自身, 高阶调用递阶 (define (f n) ( cond ((<= n 1) V) ((> n 1) (expression n fact(n-1))) )) (define (expression n m) (* (/ n 2) m)) f ( n) n / 2 ( n 1) 当 n 当 n 1时 1时 (define (expression n m) (+ n m)) 1 f 这样定义或者这样定义 f ( n) n 1 f ( n 1) 当 n 当 n 1时 1时

49 7. 运用递归和迭代 7.3 递归程序的执行过程? 49/57 49 运用递归进行程序构造 : 具有无限的自相似性步骤的表达, 自身调用自身, 高阶调用递阶

50 7. 运用递归和迭代 7.4 运用迭代进行程序构造? 50/57 50 运用迭代进行程序构造 : 具有无限的自相似性步骤的表达, 循环 - 替代 - 递推 n! n ( n 1 1)... 1 (define (fact n) (fact-iter 1 1 n)) 当 n 当 n (define (fact-iter product counter max-count) 1时 1时 (* (* (* (* (* 1 1) 2) 3) 4) n) ( cond ((> counter max-count) product) ((<= counter max-count) Product Product * Counter Counter Counter + 1 (fact-iter (* counter product) (+ counter 1) max-count ))))

51 7. 运用递归和迭代 7.5 迭代程序的执行过程? 51/57 51 运用迭代进行程序构造 : 具有无限的自相似性步骤的表达, 循环 - 替代 - 递推 (define (fact n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) ( cond ((> counter max-count) product) (fact 6) (fact-iter 1 1 6) ((<= counter max-count) (fact-iter (* counter product) (+ counter 1) max-count )))) (fact-iter (* 1 1) (+ 1 1) 6) (fact-iter 1 2 6) (fact-iter (* 1 2) (+ 2 1) 6) (fact-iter 2 3 6) (fact-iter (* 2 3) (+ 3 1) 6) (fact-iter 6 4 6) (fact-iter (* 6 4) (+ 4 1) 6) (fact-iter ) (fact-iter (* 24 5) (+ 5 1) 6) (fact-iter ) (fact-iter (* 120 6) (+ 6 1) 6) (fact-iter ) 720

52 7. 运用递归和迭代 7.6 递归与迭代的比较? 52/57 52 示例 : 求 Fibonacci 数列的算法或程序 --- 递归递归程序 (define (fib n) ( cond ((= n 0) 0) ((= n 1) 1) 递归定义 1 F( n) 1 F( n 1) F( n 2) ((> n 1) (+ (fib (- n 1)) (fib (- n 2)))) )) n 0 n 1 n 1 递归程序的执行过程

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

54 7. 运用递归和迭代 7.6 递归与迭代的比较? 无法用迭代解决的递归示例示例 : 汉诺塔问题的递归求解 ( 详解 ) 54/57 54 在世界中心贝拿勒斯 ( 在印度北部 ) 的圣庙里, 一块黄铜板上插着三根宝石针印度教的主神梵天在创造世界的时候, 在其中一根针上从下到上地穿好了由大到小的 64 片金片, 这就是所谓的汉诺塔不论白天黑夜, 总有一个僧侣在按照下面的法则移动这些金片 : 一次只移动一片, 不管在哪根针上, 小片必须在大片上面僧侣们预言, 当所有的金片都从梵天穿好的那根针上移到另外一根针上时, 世界就将在一声霹雳中消灭, 而梵塔庙宇和众生也都将同归于尽每秒钟一次, 移动完这些金片需要亿年 A B C

55 7. 运用递归和迭代 7.7 递归还有什么? 关于递归的进一步学习 55/57 55 递归是计算技术的典型特征, 是以有限的表达方式来表达无限对象实例或无限计算步骤的一种经典的计算思维递归覆盖了重复迭代和递归, 递归是最典型的构造手段递归函数是可计算函数的精确的数学描述 --- 计算理论的重要研究内容 ; 图灵机本质上也是递归 : 图灵可计算函数与递归函数等价, 凡可计算的函数都是一般递归函数 --- 丘奇 - 图灵命题 --- 计算理论的重要研究内容 ;

56 本讲小结 56/57 计算系统的构造什么是程序? 程序的本质是什么? 实例层面 : 运算组合式概念层面 : 计算系统与程序程序本质 --- 组合抽象构造与执行程序 --- 对基本动作的组合计算系统 --- 执行程序的系统递归定义递归算法递归计算程序构造的基本方法 : 递归与迭代组合 / 抽象递归函数

57 第 8 讲程序与递归 : 组合 - 抽象与构造 Questions & Discussion? 2015

<4D6963726F736F667420576F7264202D2032303132C4EAD6A4C8AFCAD0B3A1C6C0BCB6BDE1B9FBB7D6CEF6B1A8B8E62E646F6378>

<4D6963726F736F667420576F7264202D2032303132C4EAD6A4C8AFCAD0B3A1C6C0BCB6BDE1B9FBB7D6CEF6B1A8B8E62E646F6378> 鹏元资信评估证券市场评级结果分析报告 ( 截至 2012 年 12 月底 ) 一证券市场债券评级结果 1 2007 年 9 月 30 日, 鹏元资信评估 ( 简称鹏元 ) 获得中国证券监督管理委员会关于核准鹏元资信评估从事证券市场资信评级业务的批复 (