1、基本程序設(shè)計技術(shù)應(yīng)用遞歸程序設(shè)計2本章內(nèi)容n遞歸與循環(huán)n遞歸函數(shù)的執(zhí)行過程n遞歸函數(shù)效率3回憶函數(shù)定義與函數(shù)調(diào)用函數(shù)頭部函數(shù)體函數(shù)返回值類型 函數(shù)名(參數(shù)表)double DoSomething(double x) int i; double sum; sum = x; return sum; 參數(shù)和函數(shù)體內(nèi)定義的變量都稱為內(nèi)內(nèi)部變量或部變量或局部變量局部變量特殊語句return：計算表達式值，結(jié)束函數(shù)的執(zhí)行，返回表達式結(jié)果。4函數(shù)調(diào)用、執(zhí)行n函數(shù)調(diào)用n函數(shù)名(實際參數(shù)表)，如func(a,b,c);n多個參數(shù)之間用逗號分隔n函數(shù)的執(zhí)行過程n先計算各個參數(shù)(表達式)的值n進入函數(shù)體順序執(zhí)行函數(shù)

2、體語句n直到碰到return語句或執(zhí)行到最后一條語句。5函數(shù)的調(diào)用、執(zhí)行與返回t調(diào)用者程序執(zhí)行函數(shù)調(diào)用點，控制權(quán)轉(zhuǎn)移到被調(diào)用函數(shù)，原程序等待函數(shù)執(zhí)行完畢，控制返回主程序，原程序繼續(xù)被調(diào)用函數(shù)執(zhí)行6循環(huán)與遞歸n循環(huán)程序n用于描述需要重復進行計算的操作n高級語言里，也常見用遞歸來實現(xiàn)重復的計算。n遞歸n函數(shù)調(diào)用自身nC語言允許遞歸，可以在函數(shù)內(nèi)調(diào)用自身，常常使程序更簡單清晰。71. 階乘和乘冪n例：定義計算整數(shù)階乘的函數(shù)n12(n - 1)nn本例中，乘的次數(shù)依賴于n，計算所需的次數(shù)定義時無法確定。n這是一種典型循環(huán)情況n計算“次數(shù)”依賴某些參數(shù)的值。8函數(shù)(for循環(huán)方式實現(xiàn))long fact

3、1(long n) long fac, i; for (fac = 1, i = 1; i = n; i+) fac *= i; return fac;9階乘函數(shù)的精確數(shù)學定義n是一種遞歸定義的形式n要解決規(guī)模為n的問題，要先解決規(guī)模為n-1的子問題，依此類推。n如果高級語言允許遞歸定義函數(shù)，就可以直接翻譯為程序。nC允許遞歸定義n在函數(shù)定義內(nèi)直接或間接地調(diào)用被定義函數(shù)本身。nnnnn!()!101010寫成遞歸函數(shù)第一種實現(xiàn)方式：long fact (long n) return n = 0 ? 1 : n * fact(n-1);第二種實現(xiàn)方式：long fact(long n)if (n

4、 = 1) return 1;return n * fact(n - 1);11long fact(1)if (1 = 1) return 1;return 1 * fact(1 - 1);long fact(2)if (2 = 1) return 1;return 2 * fact(2 - 1);long fact(3)if (3 = 1) return 1;return 3 * fact(3 - 1);void main(void) printf(“%d”, fact(3);藍線：函數(shù)調(diào)用線路黃線：函數(shù)內(nèi)部執(zhí)行路線紅線：函數(shù)執(zhí)行結(jié)束返回主調(diào)函數(shù)的路線long fact(long n) if

5、 (n 1)nF2=F1+F0nF3=F2+F1nnn= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,nFn=1, 1, 2, 3, 5, 8, 13, 21, 34, 65, 99, 16用遞歸程序?qū)崿F(xiàn)long fib (int n) return n 2 ? 1 : fib(n - 1) + fib(n - 2);問題分析：這個程序好不好？問題分析：這個程序好不好？一方面，很好！程序與數(shù)學定義的關(guān)系很清晰，正確性容一方面，很好！程序與數(shù)學定義的關(guān)系很清晰，正確性容易確認，定義易讀易理解易確認，定義易讀易理解17例fib(5)調(diào)用過程fib(5)fib(4)fib(3)

6、fib(3)fib(2)fib(2)fib(1)fib(1)fib(0)fib(1)fib(0)fib(2)fib(1)fib(1)fib(0)存在什么問題？18問題n存在大量重復計算，參數(shù)越大重復計算越多。n重復計算會造成什么問題？n隨著參數(shù)增大，計算中重復增長迅速，最快的微機上一分鐘大約可以算出fib(45)n參數(shù)加1，fib多用近一倍時間(指數(shù)增長)。最快的微機一小時算不出fib(55)，算fib(100)要數(shù)萬年n計算需要時間，復雜計算需要很長時間。這是計算機的本質(zhì)特征和弱點。說明它不是萬能的，有些事情“不能”做。19計算復雜度n人們發(fā)現(xiàn)了許多實際問題，理論上說可用計算機解決(可寫出計

7、算它的程序)，但對規(guī)模大的情況(“大的參數(shù) n”)，人類永遠等不到計算完成。n這時能說問題解決了嗎？n計算中有一大類問題被稱為“難解問題”，其中有許多很實際的問題，如規(guī)劃、調(diào)度、優(yōu)化等。n解決這些問題或獲得實用有效的算法，需要理論和實際技術(shù)的研究。20為計算過程計時n統(tǒng)計程序或程序片段的計算時間有助于理解程序性質(zhì)。許多語言或系統(tǒng)都提供了內(nèi)部計時功能。nC語言的有關(guān)函數(shù)在time.h，統(tǒng)計程序時間時程序頭部應(yīng)寫n#include n在程序里計時，通常寫表達式nclock() / CLOCKS_PER_SECn得到從程序開始到表達式求值時所經(jīng)歷的秒數(shù)。21確定計算確定計算fib(45)fib(45

8、)所需要的時間的程序所需要的時間的程序#include #include long fib (int n) return n=1 ? 1 : fib(n-1)+fib(n-2);int main () double x; x = clock() / CLOCKS_PER_SEC; fib(45); x = clock() / CLOCKS_PER_SEC - x; printf(Timing fib(45): %f.n, x); return 0;我的筆記本計算結(jié)果：Timing fib(45): 76.000000.22Fibonacci數(shù)的迭代計算 nFibonacci數(shù)的遞推計算，易見

9、n1)f1和f2是1n2)知道fn-2和fn-1連續(xù)兩個Fibonacci數(shù)，就可算出下一個fnn遞推計算方式n逐個往后推，可用循環(huán)實現(xiàn)遞推方案long fib1 (int n) long f1 = 1, f2 = 1, f3, i; if (n = 1) return 1; for (f3 = f2 + f1, i = 2; i n; +i) f1 = f2; f2 = f3; f3 = f1 + f2; return f3;做一次遞推fnfn-1fn-224程序分析for (f3 = f2 + f1, i = 2; i n; +i) f1 = f2; f2 = f3; f3 = f1 +

10、f2; n循環(huán)結(jié)束時i等于n，這時f3的值是fn。n要得到此結(jié)論，可設(shè)法證明：每次判斷 i 的值時f3正是 Fi。25歸納證明n第一次判斷時 i的值是2，f3 的值2，正是 F2(且 f1 的值是Fi-2 (F0) ，f2 的值是Fi-1(F1)。n若某次判斷時 i 值是 k (小于n)，循環(huán)體中的語句使f1變成Fk-1 ，f2變成Fk ，f3變成Fk+1 。ni 值增 1 使我們又有f1為Fi-2 ，f2變成Fi-1 ，f3變成Fi 。n根據(jù)歸納法，每次判斷 i 的值時f3正是 Fi。26如何保證循環(huán)的正確執(zhí)行n循環(huán)實現(xiàn)重復性計算，循環(huán)體可能執(zhí)行多次。如何保證對各種數(shù)據(jù)都能正確完成計算？n循

11、環(huán)中變量不斷變化。寫循環(huán)要考慮變量間的關(guān)系，保證某些關(guān)系在循環(huán)中不變：循環(huán)的不變關(guān)系。n寫循環(huán)時最重要的就是想清循環(huán)中應(yīng)維持變量間的什么關(guān)系才能保證循環(huán)結(jié)束時變量能處在所需狀態(tài)。寫完循環(huán)后應(yīng)仔細檢查是否滿足要求。n循環(huán)不變關(guān)系(循環(huán)不變量)是理解循環(huán)、寫好循環(huán)的關(guān)鍵。27問題 n本例中用循環(huán)的函數(shù)比用遞歸定義的好嗎？n新函數(shù)在計算時間上有極大優(yōu)越性。計算時間由循環(huán)次數(shù)確定。循環(huán)體執(zhí)行次數(shù)大致為n。fib(100)只需約100次循環(huán)，幾乎察覺不到所花費時間。n新函數(shù)定義較復雜，有復雜的循環(huán)。要理解程序意義，確認函數(shù)對任何參數(shù)都算出Fibonacci值，需要借助“循環(huán)不變關(guān)系”的概念和細致分析。注

12、意：這個例子并不是說明遞歸比循環(huán)的效率低。完全可以寫出計算fib的同樣高效的遞歸定義的函數(shù)。28最大公約數(shù)n求兩個整數(shù)的最大公約數(shù)(greatest common divisor，GCD)，寫函數(shù) long gcd(long, long)n解法1n從某個數(shù)開始，逐個判斷當前數(shù)是否能同時整除m和n，在這個過程中記錄下能同時整除m和n的最大整數(shù)。n需要用一個輔助變量k記錄當前需要判斷的數(shù)。n用一個循環(huán)實現(xiàn)k順序取值n初值設(shè)為1n每次判斷完后增1n直到k大于m和n中其中的一個為止n記下循環(huán)過程中出現(xiàn)的新的m和n的公約數(shù)，作為新的最大公約數(shù)n用變量d表示當前的最大公約數(shù)n初值1(是公約數(shù))，遇到新的公

13、約數(shù)(一定更大)時記入d29程序有了d及其初值，k可以從2開始循環(huán)。函數(shù)定義long gcd (long m, long n) long d = 1, k = 2; for ( ; k = m & k = n; k+) if (m % k = 0 & n % k = 0) d = k; return d;參數(shù)互素時初值1會留下來，能保證正確30計算過程示例mnkk = m & k = nm % k = 0 & n % k = 0d208212是是是是23是是否否24是是是是45是是否否46是是否否47是是否否48是是否否49否否431特殊情況處理n一些特殊情況需

14、要處理1）m和n都為0需特殊處理。令函數(shù)返回值0；2）若m和n中一個為0，gcd是另一個數(shù)。函數(shù)的返回值正確。也可直接判斷處理；3）m、n為負時函數(shù)返回1，可能不對。n應(yīng)在循環(huán)前加語句if (m = 0 & n = 0) return 0;if (m = 0) return n;if (n = 0) return m;if (m 0) m = -m;if (n n ? n : m); /把k設(shè)為n的較小者 m % k != 0 | n % k != 0; k-) ; /* 空循環(huán)體 */return k; /*循環(huán)結(jié)束時k是最大公約數(shù) */ 33過程示例mnkm % k != 0 |

15、n % k != 0d2088是是？7是是？6是是？5是是？4否否434兩種方式比較n本方法比前一方法簡單一些。n兩種方法的共同點是重復測試。n這類方法的缺點是效率較低，參數(shù)大時循環(huán)次數(shù)很多。35解法2 輾轉(zhuǎn)相除法n求GCD有著名的歐幾里德算法(歐氏算法，輾轉(zhuǎn)相除法)。最大公約數(shù)的遞歸定義：gcd( , )modgcd( ,mod )modm nnmnn mnmn0036例n例1ngcd1(70, 30) m = 70, n = 30 m % n 10ngcd(30, 10) m = 30, n = 10 m % n 0n例2ngcd1(65, 15) m = 65, n = 15 m % n

16、 5ngcd1(15, 5) m = 15, n = 5 m % n 037遞歸程序解決n函數(shù)定義與數(shù)學定義直接對應(yīng)long gcd1 (long m, long n) return m % n = 0 ? n : gcd1(n, m % n); 假設(shè)第二個參數(shù)非0，且參數(shù)都不小于0。n對歐氏算法的研究保證了本函數(shù)能結(jié)束，對較大的數(shù)計算速度也很快，遠遠優(yōu)于順序檢查。38加入特殊情況處理long gcd(long m, long n) if (m 0) m = -m; if (n %cn, from, to); void henoi(int n,char from,char to,char by

17、) if (n = 1) moveone(from, to); else henoi(n-1, from, by, to); moveone(from, to); henoi(n-1, by, to, from); moveonemoveone定義為函數(shù)是為了方便。函數(shù)調(diào)用：定義為函數(shù)是為了方便。函數(shù)調(diào)用：henoi(6, a, b, c);henoi(6, a, b, c);48hanio(3, a, b, c); hanio(2, a, c, b); moveone(a, b); hanio(2, c, b, a);hanio(2, a, c, b) hanio(1, a, b, c);