遞歸程序設計

遞歸程序設計第1頁，共49頁，2023年，2月20日，星期四本章內(nèi)容遞歸與循環(huán)遞歸函數(shù)的執(zhí)行過程遞歸函數(shù)效率第2頁，共49頁，2023年，2月20日，星期四循環(huán)與遞歸循環(huán)程序用于描述需要重復進行計算高級語言里，也常見用遞歸來實現(xiàn)重復的計算。遞歸—recursion,recursivealgorithm函數(shù)或過程調(diào)用自身C語言允許遞歸，可以在函數(shù)內(nèi)調(diào)用自身，常常使程序更簡單清晰。第3頁，共49頁，2023年，2月20日，星期四1.階乘和乘冪例：定義計算整數(shù)階乘的函數(shù)1×2×…×(n-1)×n本例中，乘的次數(shù)依賴于n，計算所需的次數(shù)定義時無法確定。這是一種典型循環(huán)情況計算“次數(shù)”依賴某些參數(shù)的值。第4頁，共49頁，2023年，2月20日，星期四程序longfact1(longn){longfac,i;for(fac=1,i=1;i<=n;i++)fac*=i;returnfac;}第5頁，共49頁，2023年，2月20日，星期四階乘函數(shù)的精確定義是一種遞歸定義的形式要解決規(guī)模為n的問題，要先解決規(guī)模為n-1的子問題，依此類推。如果高級語言允許遞歸定義函數(shù)，就可以直接翻譯為程序。C允許遞歸定義在函數(shù)定義內(nèi)直接或間接地調(diào)用被定義函數(shù)本身。第6頁，共49頁，2023年，2月20日，星期四寫成遞歸函數(shù)longfact(longn){returnn==0?1:n*fact(n-1);}longfact(longn){if(n<=1)return1;returnn*fact(n-1);}第7頁，共49頁，2023年，2月20日，星期四longfact(1){if(1<=1)return1;return1*fact(1-1);}longfact(2){if(2<=1)return1;return2*fact(2-1);}longfact(3){if(3<=1)return1;return3*fact(3-1);}main(){printf(“%d”,fact(3));}藍線：函數(shù)調(diào)用線路黃線：函數(shù)內(nèi)部執(zhí)行路線紅線：函數(shù)執(zhí)行結(jié)束返回主調(diào)函數(shù)的路線longfact(longn){if(n<=1)return1;returnn*fact(n-1);}第8頁，共49頁，2023年，2月20日，星期四遞歸與計算過程包含遞歸的程序產(chǎn)生的計算過程和性質(zhì)更復雜，能完成很復雜的工作。遞歸調(diào)用只有一個調(diào)用表達式或語句，但是可能要許多步才能完成。實際參數(shù)的不同，會實際產(chǎn)生的遞歸調(diào)用次數(shù)（步數(shù)）也會有很大的不同。遞歸程序理解的理解比較困難遞歸的函數(shù)定義需要有條件語句去控制遞歸過程的最終結(jié)束直接給出結(jié)果的時候，遞歸結(jié)束；把對較復雜情況的計算歸結(jié)為對更簡單情況的計算，需要進行遞歸處理。第9頁，共49頁，2023年，2月20日，星期四遞歸和循環(huán)基本運算、關(guān)系判斷、條件表達式，加函數(shù)定義和遞歸定義構(gòu)成了一個（理論上）“足夠強的”的程序語言。循環(huán)程序可以改成遞歸實現(xiàn)遞歸程序也可以改成循環(huán)實現(xiàn)第10頁，共49頁，2023年，2月20日，星期四。2.Fibonacci序列計算與時間第11頁，共49頁，2023年，2月20日，星期四定義Fibonacci（斐波那契）序列的遞歸定義F0=1,F1=1Fn=Fn-1+Fn-2(n>1)1,1,2,3,5,8,13,21,34,65,99,…第12頁，共49頁，2023年，2月20日，星期四用遞歸程序?qū)崿F(xiàn)longfib(intn){returnn<2?1:fib(n-1)+fib(n-2);}問題分析：這個程序好不好？一方面，很好！程序與數(shù)學定義的關(guān)系很清晰，正確性容易確認，定義易讀易理解第13頁，共49頁，2023年，2月20日，星期四例fib(5)調(diào)用過程fib(5)fib(4)fib(3)fib(3)fib(2)fib(2)fib(1)fib(1)fib(0)fib(1)fib(0)fib(2)fib(1)fib(1)fib(0)存在什么問題？第14頁，共49頁，2023年，2月20日，星期四問題存在大量重復計算，參數(shù)越大重復計算越多。有關(guān)系嗎？隨著參數(shù)增大，計算中重復增長迅速，最快的微機上一分鐘大約可以算出fib(45)參數(shù)加1，fib多用近一倍時間(指數(shù)增長)。最快的微機一小時算不出fib(55)，算fib(100)要數(shù)萬年計算需要時間，復雜計算需要很長時間。這是計算機的本質(zhì)特征和弱點。說明它不是萬能，有些事情“不能”做。第15頁，共49頁，2023年，2月20日，星期四計算復雜度人們發(fā)現(xiàn)了許多實際問題，理論上說可用計算機解決（可寫出計算它的程序），但對規(guī)模大的情況（“大的參數(shù)n”），人類永遠等不到計算完成。這時能說問題解決了嗎？計算中有一大類問題被稱為的“難解問題”，其中有許多很實際的問題，如規(guī)劃、調(diào)度、優(yōu)化等。解決這些問題，需要理論和實際技術(shù)的研究。另外，對于許多問題的實用的有效算法，有極大的理論價值和實際價值。計算復雜性，難解問題，“P=NP？”問題。第16頁，共49頁，2023年，2月20日，星期四閱讀材料：NP問題

/NP-Problem.htmlAproblemisassignedtotheNP(nondeterministicpolynomialtime)classifitissolvableinpolynomialtimebyanondeterministicTuringmachine.AP-problem(whosesolutiontimeisboundedbyapolynomial)isalwaysalsoNP.IfaproblemisknowntobeNP,andasolutiontotheproblemissomehowknown,thendemonstratingthecorrectnessofthesolutioncanalwaysbereducedtoasingleP(polynomialtime)verification.IfPandNParenotequivalent,thenthesolutionofNP-problemsrequires(intheworstcase)anexhaustivesearch.Linearprogramming,longknowntobeNPandthoughtnottobeP,wasshowntobePbyL.

Khachianin1979.ItisanimportantunsolvedproblemtodetermineifallapparentlyNPproblemsareactuallyP.AproblemissaidtobeNP-hardifanalgorithmforsolvingitcanbetranslatedintooneforsolvinganyotherNP-problem.ItismucheasiertoshowthataproblemisNPthantoshowthatitisNP-hard.AproblemwhichisbothNPandNP-hardiscalledanNP-completeproblem.第17頁，共49頁，2023年，2月20日，星期四為計算過程計時統(tǒng)計程序或程序片段的計算時間有助于理解程序性質(zhì)。許多語言或系統(tǒng)都提供了內(nèi)部計時功能。有關(guān)函數(shù)在time.h，統(tǒng)計程序時間時程序頭部應寫#include<time.h>在程序里計時，通常寫表達式clock()/CLOCKS_PER_SEC得到從程序開始到表達式求值時所經(jīng)歷的秒數(shù)。第18頁，共49頁，2023年，2月20日，星期四確定計算fib(45)所需要的時間的程序#include<stdio.h>#include<time.h>longfib(intn){returnn<=1?1:fib(n-1)+fib(n-2);}intmain(){doublex;

x=clock()/CLOCKS_PER_SEC;fib(45);

x=clock()/CLOCKS_PER_SEC-x;printf("Timingfib(45):%f.\n",x);return0;}第19頁，共49頁，2023年，2月20日，星期四Fibonacci數(shù)的迭代計算Fibonacci數(shù)的遞推計算，易見1）f1和f2是12）知道fn-2和fn-1連續(xù)兩個Fibonacci數(shù)，就可算出下一個fn遞推計算方式逐個往后推，可用循環(huán)實現(xiàn)第20頁，共49頁，2023年，2月20日，星期四遞推方案longfib1(intn){longf1=1,f2=1,f3,i;if(n<=1)return1;for(f3=f2+f1,i=2;i<n;++i){f1=f2; f2=f3;f3=f1+f2;}returnf3;}做一次遞推fnfn-1fn-2第21頁，共49頁，2023年，2月20日，星期四程序分析for(f3=f2+f1,i=2;i<n;++i){f1=f2;f2=f3;f3=f1+f2;}循環(huán)結(jié)束時i等于n，這時c的值是fn。要得到此結(jié)論，可設法證明：每次判斷i的值時f3正是fi。第22頁，共49頁，2023年，2月20日，星期四歸納證明第一次判斷時i的值是2，f3的值2，正是fi（且f1的值是fi-1

，f2的值是fi-2）若某次判斷時i值是k（小于n），循環(huán)體中的語句使f1變成fk-1

，f2變成fk

，f3變成fk+1

。i值增1使我們又有f1為fi-2

，f2變成fi-1

，f3變成fi

根據(jù)歸納法，每次判斷i的值時f3正是fi。第23頁，共49頁，2023年，2月20日，星期四如何保證循環(huán)的正確執(zhí)行循環(huán)實現(xiàn)重復性計算，循環(huán)體可能執(zhí)行多次。如何保證對各種數(shù)據(jù)都能正確完成計算？循環(huán)中變量不斷變化。寫循環(huán)要考慮變量間的關(guān)系，保證某些關(guān)系在循環(huán)中不變：循環(huán)的不變關(guān)系。寫循環(huán)時最重要的就是想清循環(huán)中應維持變量間的什么關(guān)系才能保證循環(huán)結(jié)束時變量能處在所需狀態(tài)。寫完循環(huán)后應仔細檢查是否滿足要求。循環(huán)不變關(guān)系（循環(huán)不變量）是理解循環(huán)、寫好循環(huán)的關(guān)鍵。第24頁，共49頁，2023年，2月20日，星期四問題本例中用循環(huán)的函數(shù)比用遞歸定義的好嗎？新函數(shù)在計算時間上有極大優(yōu)越性。計算時間由循環(huán)次數(shù)確定。循環(huán)體執(zhí)行次數(shù)大致為n。fib(100)只需約100次循環(huán)，幾乎察覺不到所花費時間。新函數(shù)定義較復雜，有復雜的循環(huán)。要理解程序意義，確認函數(shù)對任何參數(shù)都算出Fibonacci值，需要借助“循環(huán)不變關(guān)系”的概念和細致分析。注意：這個例子并不是說明遞歸比循環(huán)的效率低。完全可以寫出計算fib的同樣高效的遞歸定義的函數(shù)第25頁，共49頁，2023年，2月20日，星期四最大公約數(shù)求兩個整數(shù)的最大公約數(shù)（greatestcommondivisor，GCD），寫函數(shù)longgcd(long,long)解法1從某個數(shù)開始，逐個判斷當前數(shù)是否能同時整除m和n，在這個過程中記錄下能同時整除m和n的最大整數(shù)。需要用一個輔助變量k記錄當前需要判斷的數(shù)。用一個循環(huán)實現(xiàn)k順序取值初值設為1每次判斷完后增1直到k大于m和n中其中的一個為止記下循環(huán)過程中出現(xiàn)的新的m和n的公約數(shù)，作為新的最大公約數(shù)用變量d表示當前的最大公約數(shù)初值1（是公約數(shù)），遇到新的公約數(shù)（一定更大）時記入d第26頁，共49頁，2023年，2月20日，星期四程序有了d及其初值，k可以從2開始循環(huán)。函數(shù)定義longgcd(longm,longn){longd=1,k=2;for(;k<=m&&k<=n;k++)if(m%k==0&&n%k==0)d=k;returnd;}參數(shù)互素時初值1會留下來，能保證正確第27頁，共49頁，2023年，2月20日，星期四計算過程示例mnkk<=m&&k<=nm%k==0&&n%k==0d2082是12是是23是否24是是45是否46是否47是否48是否4904第28頁，共49頁，2023年，2月20日，星期四特殊情況處理一些特殊情況需要處理1）m和n都為0需特殊處理。令函數(shù)返回值0；2）若m和n中一個為0，gcd是另一個數(shù)。函數(shù)的返回值正確。也可直接判斷處理；3）m、n為負時函數(shù)返回1，可能不對。應在循環(huán)前加語句if(m==0&&n==0)return0;if(m==0)returnn;if(n==0)returnm;if(m<0)m=-m;if(n<0)n=-n;第29頁，共49頁，2023年，2月20日，星期四可能方式2換個思路令k從某個恰當?shù)拇髷?shù)開始遞減，找到的第一個公約數(shù)就是最大公約數(shù)。k初值可取m和n中小的一個。結(jié)束條件k值達到1或找到了公約數(shù)。1總是公約數(shù)。程序主要部分可寫為：for(k=(m>n?n:m);//把k設為n的較小者

m%k!=0||n%k!=0;k--) ;/*空循環(huán)體*/returnk;/*循環(huán)結(jié)束時k是最大公約數(shù)*/第30頁，共49頁，2023年，2月20日，星期四過程示例mnkm%k!=0||n%k!=0d2088是？7是？6是？5是？4否4第31頁，共49頁，2023年，2月20日，星期四兩種方式比較本方法比前一方法簡單一些。兩種方法的共同點是重復測試。這類方法的缺點是效率較低，參數(shù)大時循環(huán)次數(shù)很多。第32頁，共49頁，2023年，2月20日，星期四解法2輾轉(zhuǎn)相除法求GCD有著名的歐幾里德算法（歐氏算法，輾轉(zhuǎn)相除法）。最大公約數(shù)的遞歸定義：第33頁，共49頁，2023年，2月20日，星期四例例1gcd1(70,30)m=70,n=30m%n10gcd(30,10)m=30,n=10m%n0例2gcd1(65,15)m=65,n=15m%n5gcd1(15,5)m=15,n=5m%n0第34頁，共49頁，2023年，2月20日，星期四遞歸程序解決函數(shù)定義與數(shù)學定義直接對應

longgcd(longm,longn) { returnm%n==0?n:gcd(n,m%n); }

假設第二個參數(shù)非0，且參數(shù)都不小于0。對歐氏算法的研究保證了本函數(shù)能結(jié)束，對較大的數(shù)計算速度也很快，遠遠優(yōu)于順序檢查。第35頁，共49頁，2023年，2月20日，星期四加入特殊情況處理longgcd(longm,longn){

if(m<0) m=-m;if(n<0) n=-n;returnn==0?m:gcd(m,n);}第36頁，共49頁，2023年，2月20日，星期四循環(huán)方法輾轉(zhuǎn)相除就是反復求余數(shù)，也是重復性工作，可可用循環(huán)結(jié)構(gòu)實現(xiàn)。出發(fā)點m和n；循環(huán)判斷m%n是否為0若是則n為結(jié)果；否則更新變量：令m取n的原值，n取m%n的原值。為正確更新需用輔助變量r，正確的更新序列：r=m%n;m=n;n=r;第37頁，共49頁，2023年，2月20日，星期四非遞歸函數(shù)定義longgcd2(longm,longn){longr;if(n==0) returnm;for(r=m%n;r!=0;r=m%n){ m=n;n=r;}returnn;}參數(shù)是局部變量，可在函數(shù)體里使用和修改。第38頁，共49頁，2023年，2月20日，星期四河內(nèi)塔（梵塔問題）第39頁，共49頁，2023年，2月20日，星期四河內(nèi)塔（hanoi塔，梵塔）問題問題出自古印度（一說西藏）某神廟有三根細柱，64個大小不等、中心有孔的金盤套在柱上，構(gòu)成梵塔。僧侶日夜不息地將圓盤從一柱移到另一柱。規(guī)則每次只移一個盤，大盤不能放到小盤上。開始時圓盤從大到小套在一根柱上，據(jù)說所有圓盤都搬到另一根柱時世界就要毀滅。第40頁，共49頁，2023年，2月20日，星期四圖示第41頁，共49頁，2023年，2月20日，星期四要求要求寫程序模擬搬圓盤過程，打印出搬動指令序列。為方便，分別將三根圓柱命名為a、b和c，假定開始時所有圓盤都在a上，要求最終搬到b。第42頁，共49頁，2023年，2月20日，星期四問題分析初看問題似乎沒規(guī)律。求解的關(guān)鍵在于看到問題的“遞歸性質(zhì)”。搬64個盤的問題可歸結(jié)為兩次搬63個盤。搬n個圓盤的問題可以歸結(jié)為搬n-1個圓盤，把n個盤從柱A搬到柱B的工作可以如下完成從柱A借助柱B將n-1個圓盤搬到柱C；將最大圓盤從柱A搬到柱B；從柱3借助柱A將n-1個圓盤搬到柱B；第43頁，共49頁，2023年，2月20日，星期四從柱A借助柱B將3個圓盤搬到柱CABCABCABCACB從柱A將最大的圓盤移動B柱從柱C借助柱A將3個圓盤搬到柱B第44頁，共49頁，2023年，2月20日，星期四voidmoveone(charfrom,charto){printf("%c->%c\n",from,to);}

voidhenoi(intn,charfrom,charto,charby){if(n==1) moveone(from,to);else{henoi(n-1,from,by,to);moveone(from,to);henoi(n-1,by,to,from);}}moveone定義為函數(shù)是為了方便。函數(shù)調(diào)用：henoi(6,'a','b','c');第45