大學計算機第6講程序與遞歸組合抽象構(gòu)造

1、第6講 程序與遞歸：組合-抽象與構(gòu)造-程序是實現(xiàn)系統(tǒng)復雜功能的一種重要-程序的本質(zhì)是組合、抽象與構(gòu)造-構(gòu)造的基本是遞歸，一種表達相似性對象及動作的無限性構(gòu)造的方法程序與遞歸：組合-抽象與構(gòu)造1. 程序的作用和本質(zhì)?2/57程序的作用和本質(zhì)-計算系統(tǒng)與程序-程序：組合、抽象與構(gòu)造1. 程序的作用和本質(zhì)1.1 怎樣設(shè)計并實現(xiàn)一個計算系統(tǒng)?3/57如何設(shè)計實現(xiàn)一個基本計算系統(tǒng)？首先，設(shè)計并實現(xiàn)系統(tǒng)可以執(zhí)行的基本動作(可實現(xiàn)的)，例如“與”動作“或”動作“非”動作“異或”動作那么，復雜的動作呢？系統(tǒng)需要提供復雜的動作復雜的動作千變?nèi)f化復雜的動作隨使用者使用目的的不同而變化復雜的動作是通過對基本動作進行

2、各種組合來實現(xiàn)的已知的基本事實是:“加減乘除運算都可轉(zhuǎn)換為加法運算來實現(xiàn)” “加法運算又可以轉(zhuǎn)換為邏輯運算來實現(xiàn)” “基本的邏輯運算與、或、非、異或等可通 過門電路予以實現(xiàn)”則基本計算系統(tǒng)可以如下實現(xiàn) 1.程序的作用和本質(zhì)1.2 什么是程序?4/57如何設(shè)計實現(xiàn)一個基本計算系統(tǒng)？程序:由基本動作指令構(gòu)造的，若干指令的一個組合或一個執(zhí)行序列，用以實現(xiàn)復雜動作復雜動作(A AND B) AND C) OR (NOT C)拆解開ANDX= A AND B X= X AND C Y= NOT C X= X OR YORNOT“非”動作指令：基本動作執(zhí)行令系統(tǒng)“與”動作“或”動作1.程序的作用和本質(zhì)1.

3、3 程序能否自動執(zhí)行?5/57如何設(shè)計實現(xiàn)一個基本的計算系統(tǒng)？程序:由基本動作指令構(gòu)造的，若干指令的一個組合或一個執(zhí)行序列，用以實現(xiàn)復雜動作復雜動作(A AND B) AND C) OR (NOT C)ANDORNOT程序執(zhí)行機構(gòu)“非”動作指令：基本動作執(zhí)行令自動解釋程序中的各種組合, 并按次序調(diào)用指令(基本動 作)予以執(zhí)行系統(tǒng)“與”動作“或”動作1.程序的作用和本質(zhì)1.4 計算系統(tǒng)與程序?6/57計算系統(tǒng) = 基本動作 + 指令 + 程序執(zhí)行機構(gòu)指令 = 對可執(zhí)行基本動作的抽象，即基本動作執(zhí)行令程序 = 基本動作指令的一個組合或執(zhí)行序列, 用以實現(xiàn)復雜的動作程序執(zhí)行機構(gòu) = 負責解釋程序即解

4、釋指令之間組合，并按次序調(diào)用指令即調(diào)用基本動作執(zhí)行的機構(gòu)復雜動作 = 基本動作的各種方式的組合程序 (Ai XOR Bi) XOR Ci(Ai XOR Bi) AND Ci) OR (Ai AND Bi) 基基本動作對基本動作的本抽象與動程序“與”動作AND作“或”動作OR執(zhí)行“非”動作NOT 指令機構(gòu)解釋這種組合, 并按次序調(diào)用基本動作予以執(zhí)行1.程序的作用和本質(zhì)1.5 程序：組合-抽象-構(gòu)造?7/57抽象： 將經(jīng)常使用的、可由低層次系統(tǒng)實現(xiàn)的一些復雜動作， 進行命名，以作為次系統(tǒng)的指令被使用一種較高抽象層次的系統(tǒng)復雜動作 = 基本動作的各種方式的組合程序(V1 + V2) x (V3 &#

5、184; V4) ¸ V5基本動作對基本動作的(V1 ¸ (V2 x (V3 + V4) - ( V5 x V6)抽象與 “加”動作+程序“減”動作- 指執(zhí)行“乘”動作x 令機構(gòu)“除”動作¸抽象一種較低抽象層復雜動作 = 基本動作的各種方式的組合次的系統(tǒng)程序 (Ai XOR Bi) XOR Ci(Ai XOR Bi) AND Ci) OR (Ai AND Bi) 基 基本動作對基本動作的本抽象與動解釋這種組合, 并程序作 “與”動作AND按次序調(diào)用基本動 執(zhí)行“或”動作OR作予以執(zhí)行機構(gòu)“非”動作NOT指令解釋這種組合, 并按次序調(diào)用基本動作予以執(zhí)行程序與遞歸：組

6、合-抽象與構(gòu)造2. 程序構(gòu)造示例(I)8/57程序構(gòu)造示例(I)-運算組合式的表達-組合、抽象與構(gòu)造-命名計算對象和構(gòu)造中使用名字及計算中以計算對象替換名字2. 程序構(gòu)造示例(I)2.1 運算組合式?9/57由數(shù)值，到基本運算組合式100205實際的數(shù)值 中綴表示法, 用運算符(即前述的指令)將兩個數(shù)值組合起來，運算符在中間(100 + 205)前綴表示法, 用運算符(即前述的指令)將兩個數(shù)值組合起來，運算符在前面(+ 100205)將運算符表示的操作應(yīng)用于后面的一組數(shù)值上，求出結(jié)果一個運算符可以表示連加，(+ 100 205 300 400 51 304)連減等情況，2. 程序構(gòu)造示例(I)

7、2.1 運算組合式?10/57由數(shù)值，到基本運算組合式(+ 100(- 200(* 200205)50)5)(* 20(- 20(+ 205554442)2)2)一起練習,書寫程序, 2. 程序構(gòu)造示例(I)2.2 如何構(gòu)造運算組合式-組合11/57運算組合式的“嵌套”及其計算過程(+ 100205)(+ (+ 60 40) (- 305 100)(* (* 3(+ (*24) (+ 35)(+ (- 107)6)計算過程(* (* 3 (+ (* 2 4) (+ 3 5) (+ (- 10 7) 6)(* (* 3 (+ 8 8) (+ 3 6)(* (* 3 16) 9 )(* 48 9

8、)4322. 程序構(gòu)造示例(I)2.3 如何用名字簡化運算組合式的構(gòu)造?-抽象12/57命名計算對象和構(gòu)造中使用名字及計算中以計算對象替換名字名字的定義：定義名字height與2關(guān)聯(lián), 以后可以用height來表示2一種類型的名字：數(shù)值型的名字(define height 2)(+ (+ height 40) (- 305 height)名字的使用(+ (* 50 height) (- 100 height)注意：不同類型的對象可以有不同的定義方法。這里統(tǒng)一用define來表示，在具體的程序設(shè)計語言中是用不同的方法來定義的2. 程序構(gòu)造示例(I)2.3 如何用名字簡化運算組合式的構(gòu)造?-抽象1

9、3/57命名計算對象和構(gòu)造中使用名字及計算中以計算對象替換名字(define pi 3.14159)(define radius 10)(*pi(* radius radius)(definecircumference(* 2 pi radius)(*circmference20)程序與遞歸：組合-抽象與構(gòu)造3. 程序構(gòu)造示例(II)14/57程序構(gòu)造示例(II)-組合、抽象與構(gòu)造-命名新運算符和構(gòu)造中使用新運算符及執(zhí)行中以過程替換新運算符-帶有條件的運算組合式3. 程序構(gòu)造示例(II)3.1 如何用名字簡化運算組合式的構(gòu)造?-抽象15/57命名新運算符和構(gòu)造中使用新運算符及執(zhí)行中以過程替換新

10、運算符(define (squarex)(* xx)名字的定義：定義名字square為一個新的運算，即過程或稱函數(shù)另一種類型的名字：運算符型的名字 x2新運算符，即過程名或函數(shù)名形式參數(shù)， 使用時將被實際參數(shù)所替代過程體，用于表示新運算符的具體計算規(guī)則，其為關(guān)于形式參數(shù)x的一種計算組合。(square(square3)6) 名字的使用注意：不同類型的對象可以有不同的定義方法。這里統(tǒng)一用define來表示，在具體的程序設(shè)計語言中是用不同的方法來定義的3. 程序構(gòu)造示例(II)3.2 程序構(gòu)造組合與抽象16/57命名新運算符和構(gòu)造中使用新運算符及執(zhí)行中以過程替換新運算符(square (squar

11、e (square(square10)名字的使用(+ 2 8)(square 3)(square (+ 2 5)(define (SumOfSquarexy)(+ (square x) (square y) x2+y2(SumOfSquare3 4)(+ (SumOfSquare34)height)3. 程序構(gòu)造示例(II)3.2 程序構(gòu)造組合與抽象17/57命名新運算符和構(gòu)造中使用新運算符及執(zhí)行中以過程替換新運算符(define (NewProca)(SumOfSquare (+ a1) (*a 2) (a+1)2+(a*2)2(NewProc3)(NewProc (+31)3. 程序構(gòu)造示

12、例(II)3.3 構(gòu)造程序的執(zhí)行求值、代入與計算18/57命名新運算符和構(gòu)造中使用新運算符及執(zhí)行中以過程替換新運算符含名字的運算組合式的計算方法：求值、代入、計算(NewProc (+31)的兩種計算過程示意先求值，再代入(NewProc (+ 3 1)(NewProc 4)(SumOfSquare (+ 4 1) (* 4 2)(SumOfSquare 5 8)(+ (Square 5) (Square 8)(+ (* 5 5) (* 8 8)(+ 25 64)893. 程序構(gòu)造示例(II)3.3 構(gòu)造程序的執(zhí)行求值、代入與計算19/57命名新運算符和構(gòu)造中使用新運算符及執(zhí)行中以過程替換新運

13、算符含名字的運算組合式的計算方法：代入、求值、計算(NewProc (+31)的兩種計算過程示意先代入，后求值代入階段求值階段(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)(+ 25 64)893.

14、程序構(gòu)造示例(II)3.4 有條件的運算如何表達?20/57帶有條件的運算組合式(define (abs x) (cond (>(=(< xx 0)x 0)0) (-x)0) x)(cond ( <p1> <e1>)( <p2> <e2>).( <pn> <en>) )3. 程序構(gòu)造示例(II)3.5 你能表達與構(gòu)造程序嗎?21/57u 問題1：用前綴表示法書寫下述表達式10 + 4 + (8- (12 - (6 + 4¸5)3*(6-2)(12-7)u 問題2：請定義一個過程，求某一數(shù)值的立方 a3

15、u 問題3：進一步以問題2定義的過程，再定義一個過程，求某兩個數(shù)值的立方和。 a3+b3進一步求 53+83，并模擬給出計算過程。3. 程序構(gòu)造示例(II)3.5 你能表達與構(gòu)造程序嗎?22/57u 問題4：請定義一個過程，計算下列函數(shù)ì- xx > 0x = 0x < 0x2if ififf (x) = ï0íï- x2 + xî(define(fx) (cond(>x0)x 0)(- 0)(-(Square x)0)x)(=(<xx(Square x) )(cond ( <p1> <e1>)(

16、 <p2> <e2>).( <pn> <en>) )程序與遞歸：組合-抽象與構(gòu)造4. 遞歸的概念23/57遞歸的概念-為什么需要遞歸-遞歸能解決什么問題4. 遞歸的概念4.1 為什么需要遞歸?2424/57遞歸(Recursion) (* (* (* (* (* 11) 2) 3) 4) n) “從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？(從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？(從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？(從前)”怎樣在表達中

17、既去掉省略號，而又能表達近乎無限的內(nèi)容4. 遞歸的概念4.2 什么情況需要遞歸?2525/57遞歸的典型視覺形式-自相似性事物的無限重復性構(gòu)造4. 遞歸的概念4.2 什么情況需要遞歸?2626/57遞歸的典型視覺形式-自相似性事物的無限重復性構(gòu)造4. 遞歸的概念4.3 如何表達延續(xù)不斷卻相似或重復的事物或過程?2727/57數(shù)學中的遞推式u 一個數(shù)列的第n項an與該數(shù)列的其他一項或多項之間存在某種對應(yīng)關(guān)系，被表達為一種公式，稱為遞推式等差數(shù)列的產(chǎn)生a =50a1=a0+3 = 8a =a +3 = 1121a3=a2+3 = 14a4=a3+3 = 17 第1項(或前K項)的值是已知的 遞推基

18、礎(chǔ)； 由第n項或前n項計算第n+1項遞推規(guī)則/遞推步驟； 由前向后，可依次計算每一項等差數(shù)列遞推公式a0=5an=an-1+ 3當n>=1時等比數(shù)列遞推公式a0=5an=an-1´ 20當n>=1時4. 遞歸的概念4.3 如何表達延續(xù)不斷卻相似或重復的事物或過程?2828/57數(shù)學中的數(shù)學歸納法u 數(shù)學歸納法是一種用于證明與自然數(shù)有關(guān)法能用有限的步驟解決無窮對象的論證問題。題正確性的證明方法，該方u 由歸納基礎(chǔ)和歸納步驟：l 假定對一切正整數(shù)n, 有一個命題P(n),若以下證明成立, 則P(n)為真。l (1)歸納基礎(chǔ): 證明P(1)為真；l (2)歸納步驟: 證明對任意

19、的i，若P(i)為真，則P(i+1)也為真。求證命題P(n) “從1開始連續(xù)n個奇數(shù)之和是n的平方” 即公式： 1+3+5+ (2n-1) =n2成立。證明:(1) 歸納基礎(chǔ): 當n=1時, 等式成立即1=1;(2) 歸納步驟: 設(shè)對任意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)也成立，根據(jù)數(shù)學歸納法該命題得證。 證畢。4. 遞歸的概念4.4 什么是遞歸?29/57什么是遞歸?遞歸的思想源于數(shù)學的遞推式和數(shù)學歸納法。遞歸是一種表達相似性對象及

20、動作的無限性構(gòu)造的方法。u 遞歸是一種關(guān)于抽象的表達方法-用遞歸定義無限的相似事物u 遞歸是一種算法或程序的構(gòu)造技術(shù)-自身調(diào)用自身，高階調(diào)用低階，構(gòu)造無限的計算步驟u 遞歸是一種典型的計算過程-由后向前代入，再由前向后計算遞歸n 遞歸基礎(chǔ)：定義、構(gòu)造和計算的起點，直接給出；n 遞歸步驟：由前n項或第n項定義第n+1項；由低階f(k)且k<n，來構(gòu)造高階f(n+1)-執(zhí)行：由后向前代入，直至代入到遞歸基礎(chǔ)，再由遞歸基礎(chǔ)向后計算直至計算出最終結(jié)果；程序與遞歸：組合-抽象與構(gòu)造5. 原始遞歸30/57原始遞歸-原始遞歸：復合(組合)與構(gòu)造5. 原始遞歸5.1 原始遞歸函數(shù)及其遞歸基礎(chǔ)?3131

21、/57原始遞歸函數(shù)是接受自然數(shù)x或自然數(shù)的元組(x1,xn)作為參數(shù)，并產(chǎn)，記為f(x)或f(x1,xn)。接受n個參數(shù)的函數(shù)稱作n元生自然數(shù)的一個函數(shù)。處處有定義的函數(shù)被稱作全函數(shù)，未必處處有定義的函數(shù)稱作半函數(shù)或部分函數(shù)。最基本的原始遞歸函數(shù)，也被稱原函數(shù)有三個：(1) 初始函數(shù)：0元函數(shù)即常數(shù)無需計算；或者常數(shù)函數(shù)：對于每個自然數(shù)n和所有的k, 有f(x1,x2,xK)=n。(2) 后繼函數(shù)：1 元后繼函數(shù)S，它接受一個參數(shù)并返回給出參數(shù)的后繼數(shù)例如S(1)=2, , S(x) = x+1, 其中x為任意自然數(shù)。(3) 投影函數(shù)：對于所有n1 和每個 1in 的i，n 元投影函數(shù)Pi ，

22、它接受nn 個參數(shù)并返回它們中的第i 個參數(shù)，即Pi(x1，x2，xn) = xin5. 原始遞歸5.2 原始遞歸函數(shù)如何構(gòu)造組合/復合?3232/57(1)復合：給定原始遞歸函數(shù) f(x1,.,xk)，和 k 個原始遞歸函數(shù)g1,.,gk，則f 和g1,.,gk的復合是 函數(shù)h, 即h(x1,.,xm) = f(g1(x1,.,xm),.,gk(x1,.,xm)簡單而言，復合是將一系列函數(shù)作為參數(shù)代入到另一個函數(shù)中，又被稱為代入。復合是構(gòu)造新函數(shù)的法。復合是表達組合的法。結(jié)構(gòu)f vs. 構(gòu)件g1,gkg1,gk的組合關(guān)系f vs. 運算組合式g1,gkg1,gk的指令組合關(guān)系f vs. 基本

23、指令g1,gk5. 原始遞歸5.2 原始遞歸函數(shù)如何構(gòu)造組合/復合?3333/57(2)原始遞歸：給定原始遞歸函數(shù) f 和g，則新函數(shù)h可由f 和g遞歸的定義，其中h(0,x1,.,xk) = f(x1,.,xk)h(S(n), x1,.,xk) = g(h(n,x1,.,xk)，n，x1,.,xk)簡單而言，定義新函數(shù)h，就是要定義h(0), h(1),h(n),。h(0)直接給出。h(n+1)則由將h(n)和n代入g中來構(gòu)造。原始遞歸是遞歸地構(gòu)造新函數(shù)的方法，尤其是無限的相似性函數(shù)的構(gòu)造方法。(* (* (* (* (*1 1) 2) 3) n) S(n)h(0) = 1h(1) = g(

24、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)g(x1, x2) = (* x1S(x2)h(0) = 1h(S(n) = g(h(n), n)5. 原始遞歸5.3 原始遞歸函數(shù)構(gòu)造示例?3434/57原始遞歸函數(shù)的構(gòu)造示例p 已知：f(x)=xg(x1,x2,x3)=x1+x2+x3, 其中x,x1,x2,x3均為自然數(shù)h(0,x) = f(x)且 h(S(n), x) = g(h(n,x),n,x)該函數(shù)對任一自然數(shù)的計算過程

25、為：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 原始遞歸函數(shù)構(gòu)造示例?3535/57原始遞歸函數(shù)的構(gòu)造示例p 已知：f(x)=2g(x1,x2,x

26、3)=x1,其中x,x1,x2,x3均為自然數(shù)h(0,x) = f(x)且 h(S(n), x) = g(h(n,x),n,x)該函數(shù)對任一自然數(shù)的計算過程為：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)

27、= = 2 程序與遞歸：組合-抽象與構(gòu)造6. 遞歸與迭代36/57遞歸與迭代-兩種不同的遞歸函數(shù)-遞歸與迭代6. 遞歸與迭代6.1 兩種不同的遞歸函數(shù)?3737/57遞歸和遞推：比較下面兩個示例p Fibonacci數(shù)列，無窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：n = 0ì1F (n) = ïn = 1n > 11í 遞歸定義ïF (n -1) + F (n - 2)îF(0)=1;F(1)=1; F(2)=F(1)+F(0)=2;F(3)=F(2)+F(1)= 3;F(4)

28、=F(3)+F(2)= 3+2=5; 遞推計算/迭代計算/迭代執(zhí)行 定義是遞歸的, 但執(zhí)行可以是遞歸的也迭代的2N226. 遞歸與迭代23838/57n6.1 兩種不同的遞歸函數(shù)?遞歸和遞推：比較下面兩個示例p 阿克曼遞歸函數(shù)-雙遞歸函數(shù)p 阿克曼給出了一個不是原始遞歸的可計算的全函數(shù)。表述如下：A(1,0) = 2A(0, m) = 1A(n,0) = n + 2A(n, m) = A( A(n -1, m), m -1) 遞歸定義函數(shù)本身是遞歸的，函數(shù)的變量也是遞歸的m ³ 0n ³ 2n, m ³ 1m=0時，A(n,0)=n+2；m=1時，A(n,1)=A

29、(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。 遞歸計算/遞歸執(zhí)行22N22m=3時，類似的可以推出由后向前代入，再由前向后計算n6. 遞歸與迭代6.1 兩種不同的遞歸函數(shù)?3939/57遞歸和遞推：比較下面兩個示例p 阿克曼遞歸函數(shù)-雙遞歸函數(shù)-另一種形式n + 1若m = 0若n = 0若m, n > 0ìA(m, n) = ïA(m -1),1)íï

30、A(m -1, A(m, n -1)î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)

31、 =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.2 遞歸和迭代有什么差別?4040/57遞歸和迭代(遞推)u 迭代(遞推)：可以由前向后依次計算或直接計算u 遞歸：可以由前向后依次計算或直接計算；但有些，只能由后向前代入，然后再由前向后計算。u 遞歸包含了遞推，但遞推不能覆蓋遞歸。程序與遞歸：組合-抽象與構(gòu)造7. 運用遞歸與迭代41/57運用遞歸與迭代-用遞歸方法進行定義-用遞歸方法和迭代方法構(gòu)造程序

32、7. 運用遞歸和迭代7.1 運用遞歸進行無限對象的定義?4242/57運用遞歸定義無限自相似性對象u 示例：算術(shù)表達式的遞歸定義。 ( (100 + (X + Y) * (Z-Y) + Z) ) 首先給出遞歸基礎(chǔ)的定義：(1)任何一個常數(shù)C是一個算術(shù)表達式； (2)任何一個變量V是一個算術(shù)表達式； 再給出遞歸步驟：(3) 如F、G是算術(shù)表達式，則下列運算： F+G，F(xiàn)-G，F(xiàn)*G，F(xiàn)/G是算術(shù)表達式；(4) 如F是表達式，則(F)亦是算術(shù)表達式。(5) 括號內(nèi)表達式優(yōu)先計算，“*”與“/”運算優(yōu)先于“+”與“-”運算(6)算術(shù)表達式僅限于以上形式。7. 運用遞歸和迭代7.1 運用遞歸進行無限對

33、象的定義?4343/57運用遞歸定義無限自相似性對象u 示例：“祖先”的遞歸定義(1) 的雙親是他的祖先（遞歸基礎(chǔ)）。(2) 祖先的雙親同樣是的祖先（遞歸步驟）。7. 運用遞歸和迭代7.1 運用遞歸進行無限對象的定義?4444/57運用遞歸定義無限自相似性對象u 示例：簡單命題邏輯的形式化遞歸定義 ( (M or (X and Y) and (Y or K) and Z) ) (1) 一個命題是其值為真或一個語句（遞歸基礎(chǔ)）。(2) 如果X是一個命題，Y也是一個命題，則X and Y，X or Y, Not X也是一個命題。（遞歸步驟）。(3) 如果X是一個命題，則(X)也是一個命題，括號內(nèi)題

34、運算優(yōu)先。(4) 命題由以上方式構(gòu)造。7. 運用遞歸和迭代7.1 運用遞歸進行無限對象的定義?4545/57運用遞歸定義無限自相似性對象u 示例：樹的形式化遞歸定義樹是包含若干個元素的有窮集合，每個元素稱為結(jié)點。其中：(1) 有且僅有一個特定的稱為根的結(jié)點；(遞歸基礎(chǔ))(2) 除根結(jié)點外的其余結(jié)點可被分為k個互不相交的集合T1, T2,Tk(k³0)，其中每一個集合Ti本身也是一棵樹，被稱其為根的子樹。(遞歸步驟)7. 運用遞歸和迭代7.2 運用遞歸進行程序構(gòu)造?4646/57運用遞歸進行程序構(gòu)造：具有無限的自相似性步驟的表達，自身調(diào)用自身，高階調(diào)用遞階u 示例：求n!的算法或程序當

35、n £ 1時當n > 1時n != ì1íîn ´ (n - 1) ´ . ´1當n £ 1時當n > 1時n != ì1íîn ´ (n - 1)!7. 運用遞歸和迭代7.2 運用遞歸進行程序構(gòu)造?4747/57運用遞歸進行程序構(gòu)造：具有無限的自相似性步驟的表達，自身調(diào)用自身，高階調(diào)用遞階u 示例：求n!的算法或程序 -用遞歸方法構(gòu)造當n £ 1時當n > 1時n != ì1íîn ´ (n - 1)!(d

36、efine(factn) ( cond(<=n 1) 1)(>n1)(*nfact(n-1) )7. 運用遞歸和迭代7.2 運用遞歸進行程序構(gòu)造?4848/57運用遞歸進行程序構(gòu)造：具有無限的自相似性步驟的表達，自身調(diào)用自身，高階調(diào)用遞階(define(fn)( cond(<=n1)V)(>n1)(expressionnfact(n-1) )(define(expressionnm)(*(/n2)m)這樣定義f (n) = ì當n £ 1時當n > 1時1íîn / 2´ f (n -1)(define(expre

37、ssion nm)(+nm)或者這樣定義當n £ 1時當n > 1時f (n) = ì1íîn + f (n -1)7. 運用遞歸和迭代7.3 遞歸程序的執(zhí)行過程?4949/57運用遞歸進行程序構(gòu)造：具有無限的自相似性步驟的表達，自身調(diào)用自身，高階調(diào)用遞階7. 運用遞歸和迭代7.4 運用迭代進行程序構(gòu)造?5050/57運用迭代進行程序構(gòu)造：具有無限的自相似性步驟的表達，循環(huán)- 替代-遞推當n £ 1時n != ì1íîn ´ (n - 1) ´ . ´1當n > 1時4)

38、n)(*(* (*(*(* 1 1) 2)3)(define (fact n) (fact-iter 1 1 n)(define (fact-iter product counter max-count)( cond (>counter max-count) product)(<=counter max-count)(fact-iter (* counter product) (+ counter 1)max-count )Product ç Product * CounterCounter ç Counter + 17. 運用遞歸和迭代7.5 迭代程序的執(zhí)行過程?5151/57運用迭代進行程序構(gòu)造：具有無限的自相似性步驟的表達，循環(huán)-替代-遞推(fact 6)è (fact-iterè (fact-iterè (fact-iterè (fact-iterè (fact-iterè (fact-iterè (fact-iterè 7201(*(*(*(*(*(*111266)1)2)3)4)è (fact-iterè (f