遞歸程序設(shè)計(jì)

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

/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頁(yè)，共49頁(yè)，2023年，2月20日，星期四為計(jì)算過(guò)程計(jì)時(shí)統(tǒng)計(jì)程序或程序片段的計(jì)算時(shí)間有助于理解程序性質(zhì)。許多語(yǔ)言或系統(tǒng)都提供了內(nèi)部計(jì)時(shí)功能。有關(guān)函數(shù)在time.h，統(tǒng)計(jì)程序時(shí)間時(shí)程序頭部應(yīng)寫(xiě)#include<time.h>在程序里計(jì)時(shí)，通常寫(xiě)表達(dá)式clock()/CLOCKS_PER_SEC得到從程序開(kāi)始到表達(dá)式求值時(shí)所經(jīng)歷的秒數(shù)。第18頁(yè)，共49頁(yè)，2023年，2月20日，星期四確定計(jì)算fib(45)所需要的時(shí)間的程序#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頁(yè)，共49頁(yè)，2023年，2月20日，星期四Fibonacci數(shù)的迭代計(jì)算Fibonacci數(shù)的遞推計(jì)算，易見(jiàn)1）f1和f2是12）知道fn-2和fn-1連續(xù)兩個(gè)Fibonacci數(shù)，就可算出下一個(gè)fn遞推計(jì)算方式逐個(gè)往后推，可用循環(huán)實(shí)現(xiàn)第20頁(yè)，共49頁(yè)，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頁(yè)，共49頁(yè)，2023年，2月20日，星期四程序分析for(f3=f2+f1,i=2;i<n;++i){f1=f2;f2=f3;f3=f1+f2;}循環(huán)結(jié)束時(shí)i等于n，這時(shí)c的值是fn。要得到此結(jié)論，可設(shè)法證明：每次判斷i的值時(shí)f3正是fi。第22頁(yè)，共49頁(yè)，2023年，2月20日，星期四歸納證明第一次判斷時(shí)i的值是2，f3的值2，正是fi（且f1的值是fi-1

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

，f2變成fk

，f3變成fk+1

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

，f2變成fi-1

，f3變成fi

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

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

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

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

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