【正文】 語句塊 判斷遞歸結(jié)束的條件， else 語句塊 處理遞歸的情況。 遞歸 的實質(zhì) 體現(xiàn)在函數(shù) Fa ctor oa l() 的自身調(diào)用上。 遞歸思想，我們先給出一個簡單的例子。 例 計算 5 6 計算方法之一： 6 ， 6+ 6= 12 ， 12 + 6= 18 ， 18+ 6= 24 ， 24+ 6= 30 。 計算方法之二： 5 6 ， 4 6 ， 3 6 ， 2 6 ， 1 6 ； 1 6+ 6= 12 ， 12+ 6= 18 ， 18+ 6= 24 ， 24+ 6= 30 ； 這個例子還可以用更一般的遞歸關(guān)系表示： n n 1a = C a + g (n ) n = 2,3,4, ? 其中： C 是已知常數(shù)， { g(n) } 是一個已知數(shù)列。 如果已知n1a?就可以確定na， 從 數(shù)學(xué)歸納法的角度來看，這相當于數(shù)學(xué)歸納法歸納步驟的內(nèi)容。 但僅有這個關(guān)系還不能確定這個數(shù)列，若使它完全確定，還應(yīng)給出這個數(shù)列的初始值 a1 遞歸和數(shù)學(xué)歸納法 ?與數(shù)學(xué)歸納法相對應(yīng)，遞歸由遞歸基礎(chǔ)和遞歸步驟兩部分組成。 ?數(shù)學(xué)歸納法是一種論證方法。 ?而遞歸是算法和程序設(shè)計的一種實現(xiàn)技術(shù)。 ?涉及遞歸定義的證明通常采用數(shù) 學(xué)歸納法，數(shù) 學(xué)歸納法是遞歸的基礎(chǔ)。 1a定義序列 例 5. 2 2 現(xiàn)有序列： 2 ， 5 ， 11 ， 23 ，? , na=2n 1a+1, ?。 請給出其遞歸定義。 解：該序列的遞歸定義如下： n n 1a 2 a 1?? 1a =2 n = 1 ； 遞歸基礎(chǔ) na =2n 1a +1 ， n = 2 ， 3 ， 4 ，?； 遞歸步驟 定義函數(shù) 例 5 – 23 ， 給出階乘： F (n) = n ! 的遞歸定義。 解： 階乘 F (n) = n ! 的遞歸定義如下： F (0)= 1 遞歸基礎(chǔ) F (n) =n F (n 1) ， n =1,2 ,3, ? 。 遞歸步驟 定義集合 例 現(xiàn)有文法 G 的生成式如下： S → 0 A 1 ； S 是文法 G 的開始符號 A → 01 ； 遞歸基礎(chǔ) A → 0 A 1 ； 遞歸步驟 以上這個文法的生成式采用了遞歸方法，該文法其實定義了這樣一個集合： L(G)={0n1n|n≥1｝ , 這是一個以相同個數(shù)的“ 0”和“ 1”組成的字符串的集合，即一種特殊的語言。 阿克曼函數(shù)： ?????n + 1A ( m , n ) = A ( ( m 1), 1)A A ( m , n 1)( m 1, ) m = 0n = 0m , n 0若 若 若 解阿克曼函數(shù)的遞歸算法 : Be gin if m=0 th en n+1 el se if n =0 the n A(m 1,1 ) el se A(m 1, A(m ,n 1) ) // 自身調(diào)用的遞歸過程 En d 大家完成作業(yè)題： 例 計算 A(1,2) 解 : 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 應(yīng)注意：這里的阿克曼函數(shù)是一個二元（ m， n）遞歸函數(shù)。 ?????n + 1A ( m , n ) = A ( ( m 1), 1)A A ( m , n 1)( m 1, )m = 0n = 0m , n 0若 若 若 迭代與遞歸有著密切的聯(lián)系，比如 ： 序列 0Xa ?，n1X ( n )f?? 的遞歸關(guān)系也可以看作是數(shù)列的 迭代關(guān)系。 遞歸 與 迭代 雖然 本質(zhì) 相同，但實際還是有一些差別。 遞歸是利用以前的結(jié)果 ，利用遞歸的調(diào)用實施計算， 如： 利用S( n 1 )計算S( n )，要得到S( n 1 )，就 必須進一步“ 遞歸 ”S( n 2 ) S ( n 3 )??，直到“遞歸”到初始項 S( 1 )，最終計算出S( n )； 而迭代 通常 是 調(diào)用相同的子程序 ，也利用“以前”的結(jié)果 Sn 1，但 Sn 1不直接參與 Sn的計算，而僅作為與迭代結(jié)束的條件“ ε ”進行比較的依據(jù)。 即 ：使 |Sn Sn 1| ε 滿足 精度的要求，計算就結(jié)束 。 否則，繼續(xù)計算 Sn，直到滿足迭代條件為止。 迭代程序都可以轉(zhuǎn)換為與它等價的遞歸程序 ； 反之，則不然。 平面幾何的公理化概括（歐氏幾何）。 原始概念：點、線、面； 原始命題：公設(shè)和公理如下： 公設(shè) 1：兩點之間可作一條直線； 公設(shè) 2：一條有限直線可不斷延長； 公設(shè) 3：以任意中心和直徑可以畫圓； 公設(shè) 4：凡直角都彼此相等； 公設(shè) 5：在平面上，過給定直線之外的一點，存在且僅存在一條平行線。 即所謂的 “ 平行公設(shè)（公理） ” 。 公理 1：等于同量的量彼此相等 。 公理 2：等量加等量和相等 。 公理 3：等量減等量差相等 。 公理 4： 彼此重合的圖形全等 。 公理 5: 整體大于部分。 平面幾何的一切公式和定理都必須且只能由上述公理系統(tǒng)推出 ?由于公理化方法把一門數(shù)學(xué)（某一領(lǐng)域）基礎(chǔ)分析得清清楚楚，結(jié)構(gòu)謹嚴有序，這就有利于比較各門數(shù)學(xué)在實質(zhì)上的異同，從而促進和推動新理論的產(chǎn)生。 ?“ 歐氏幾何 ”和“ 非歐幾何 ”就是在研究和使用公理化方法的過程中產(chǎn)生的。由于數(shù)學(xué)公理化方法表述數(shù)學(xué)理論的簡潔性、條理性和結(jié)構(gòu)的和諧性，從而為其它科學(xué)理論的表述起到了示范作用。 ?其它科學(xué)紛紛效法數(shù)學(xué)公理化建造理論的模式，出現(xiàn)了各種理論的公理化系統(tǒng)，如理論力學(xué)公理化，相對論公理化以及科學(xué)計算領(lǐng)域的公理化等等。 ?為了保證公理系統(tǒng)的無矛盾性和獨立性，一般要盡可能使公理系統(tǒng)簡單化。簡單化將使無矛盾性和獨立性的證明成為可能。簡單化是科學(xué)研究追求的目標之一。一般而言，正確的一定是簡單的（注意，這句話是單向的，反之不一定成立）。 ?關(guān)于公理系統(tǒng)的完備性要求，自哥德爾發(fā)表關(guān)于形式系統(tǒng)的不完備性定理 （針對希爾波特（ Hilbert）的“ 證明論 試圖將一切數(shù)學(xué)問題都形式化，并進行嚴格典范證明 ” ） 的論文后，數(shù)學(xué)家們對公理系統(tǒng)的完備性要求大大放寬了，也就是說能完備更好，即使不完備同樣也具有重要的價值。 ?在歐氏幾何公理系統(tǒng)中，原始概念（點、線、面）和所有的公理都有直觀的背景或客觀的意義，像這樣有現(xiàn)實世界背景的公理系統(tǒng)，一般被稱為具體公理系統(tǒng)（以歐幾里德的 《 幾何原本 》 為代表）。 ?由于非歐幾何的出現(xiàn)，使人們感到具體公理系統(tǒng)過于受直覺的局限，因而，在 19世紀末和 20世紀初，一些杰出的數(shù)學(xué)家（ Hilbert）和邏輯學(xué)家（ Godel）開始了對抽象公理系統(tǒng)的研究 。 ?在抽象公理系統(tǒng)（以 Hilbertd的 《 幾何基礎(chǔ) 》 為代表）中，原始概念的直覺意義被忽視，甚至沒有任何預(yù)先設(shè)定的意義。而公理也無需以任何實際意義為背景，它們無非是一些形式約定的符號串。這時抽象公理系統(tǒng)可以有多種解釋。 ?形式系統(tǒng)由下面幾個部分組成： ?⑴ 初始符號：初始符號不具有任何意義。 ?⑵ 形式規(guī)則：形式規(guī)則規(guī)定一種程序借以判定哪些符號串是本系統(tǒng)中的，公式哪些不是。 ?⑶ 公理：即在本系統(tǒng)的公式中確定不加推導(dǎo)就可以斷定的公式集。 ?⑷ 變形規(guī)則：變形規(guī)則亦稱演繹規(guī)則或推導(dǎo)規(guī)則。 ?形式系統(tǒng)由形式語言和定義于其上的演繹結(jié)構(gòu)組成。 ?計算機系統(tǒng)的軟、硬件都是一種形式系統(tǒng)，它們的結(jié)構(gòu)也可以用形式化方法描述。 ?程序設(shè)計語言更是不折不扣的形式語言系統(tǒng)。 形式系統(tǒng) 的局限性 ⑴、不完備性 ： 1931 年，哥德爾提出的關(guān)于形式系統(tǒng)的“不完備性定理”指出：如果一個形式的數(shù)學(xué)理論是足夠復(fù)雜的（復(fù)雜到所有的遞歸函數(shù)在其中都能夠表示）而且，它是無矛盾的，那么 在這一理論中存在一個語句，而這一語句在這一理論中是既不能證明也不能否證的。 ⑵、不可判定性：如果對一類語句 C 而言，存在一個算法 AL ，使得對 C 中的任一語句 S 而言，可以利用算法 AL 來判定其是否成立，則 C 稱為可判定的；否則，稱為不可判定的。 著名的停機問題就是一個不可判定性的問題。 該問題是指：一個任給的圖靈機，對于一個任給的輸入而言是否停機的問題。圖靈證明這類問題是不可判定的。 需要指出的是：計算機系統(tǒng)就是一種形式系統(tǒng)。 因此計算機系統(tǒng)一樣也具有形式系統(tǒng)的局限性。