函數(shù)遞歸與調(diào)用

關(guān)于函數(shù)遞歸與調(diào)用第1頁(yè)，共33頁(yè)，2023年，2月20日，星期三

函數(shù)的遞歸調(diào)用遞歸:

一個(gè)函數(shù)直接或間接地使用自身。

1.直接遞歸調(diào)用：函數(shù)直接調(diào)用本身

2.間接遞歸調(diào)用：函數(shù)間接調(diào)用本身第2頁(yè)，共33頁(yè)，2023年，2月20日，星期三情景1：小時(shí)候，我們聽(tīng)過(guò)這樣的故事：從前有座山，山上有座廟，廟里有個(gè)老和尚給小和尚講故事，講的什么故事呢？從前有座山，山上有座廟，廟里有個(gè)老和尚給小和尚講故事，講的什么故事呢？從前有座山，山上有座廟，廟里有個(gè)老和尚給小和尚講故事，講的什么故事呢？……故事可以一直講下去，每一個(gè)故事內(nèi)容都相同，但卻是故事里的故事。程序設(shè)計(jì)中，函數(shù)A自己調(diào)用自己，稱(chēng)為直接遞歸調(diào)用。第3頁(yè)，共33頁(yè)，2023年，2月20日，星期三情景2：鏡子A和鏡子B相對(duì)放在一起，你會(huì)發(fā)現(xiàn)什么現(xiàn)象呢？對(duì)了，我們會(huì)發(fā)現(xiàn)鏡子A中有鏡子B的映象，鏡子B中又鏡子A的映象，這樣層層疊疊，無(wú)窮無(wú)盡。AB在程序設(shè)計(jì)中，像這種函數(shù)A調(diào)用函數(shù)B,函數(shù)B再反過(guò)來(lái)調(diào)用函數(shù)A的算法，稱(chēng)為間接遞歸調(diào)用。第4頁(yè)，共33頁(yè)，2023年，2月20日，星期三

遞歸算法的特點(diǎn)：①遞歸函數(shù)的執(zhí)行過(guò)程比較復(fù)雜，往往都存在著連續(xù)的遞歸調(diào)用，其執(zhí)行過(guò)程可分為“遞推”和“回歸”兩個(gè)階段，先是一次一次不斷的遞推過(guò)程，直到符合遞推”結(jié)束條件，然后是一層一層的回歸過(guò)程。②而其中的每一次遞歸調(diào)用，系統(tǒng)都要在棧中分配空間以保存該次調(diào)用的返回地址、參數(shù)、局部變量，因此在遞推階段，?？臻g一直處于增長(zhǎng)狀態(tài)，然后進(jìn)入回歸階段，?？臻g反向依次釋放。直到“遞推”過(guò)程的終止，③在遞歸的執(zhí)行過(guò)程中，遞歸結(jié)束條件非常重要，它控制“遞推”過(guò)程的終止，在任何一個(gè)遞歸函數(shù)中，遞歸結(jié)束條件都是必不可少的，否則將會(huì)一直“遞推”下去。導(dǎo)致無(wú)窮遞歸。遞歸算法的缺點(diǎn)：內(nèi)存消耗巨大，且連續(xù)地調(diào)用和返回操作占用較多的CPU時(shí)間。遞歸算法的優(yōu)點(diǎn)：算法描述簡(jiǎn)潔易懂。第5頁(yè)，共33頁(yè)，2023年，2月20日，星期三

思考如下問(wèn)題：例1:

有5個(gè)人坐在一起,問(wèn)第5個(gè)人多少歲,他說(shuō)比第4個(gè)人大2歲;問(wèn)第4個(gè)人歲數(shù),他說(shuō)比第3個(gè)人大2歲;問(wèn)第3個(gè)人,又說(shuō)比第2個(gè)大2歲;問(wèn)第2個(gè)人，說(shuō)比第1個(gè)人大2歲；最后問(wèn)第1個(gè)人，他說(shuō)他10歲；請(qǐng)問(wèn)第5個(gè)人多大?比她大2歲比她大2歲比她大2歲比她大2歲我10歲第6頁(yè)，共33頁(yè)，2023年，2月20日，星期三分析：要求第5個(gè)人的年齡，就必須先知道第4個(gè)人的年齡，而第4個(gè)人的年齡也不知道，要求第4個(gè)人的年齡必須先知道第3個(gè)人的年齡，而第3個(gè)人的年齡又取決于第2個(gè)人的年齡，第2個(gè)人的年齡取決于第1個(gè)人的年齡。而且每一個(gè)人的年齡都比其前1個(gè)人的年齡大2。第一個(gè)人的年齡已知，根據(jù)第一個(gè)人的年齡可依次求得第二、三、四、五個(gè)人的年齡。這就是一個(gè)遞歸問(wèn)題。而每一個(gè)人的年齡都比其前1個(gè)人的年齡大2

就是遞歸成立的條件，也就是遞歸公式。age（5）=age（4）＋2age（4）=age（3）＋2age（3）=age(2）+2age（2）＝age(1）＋2age（1）＝10

可以用式子表述如下：

age（n）=10（n=1）

age（n）=age（n-1)+2（n＞1）可以看到，當(dāng)n＞1時(shí)，求第n個(gè)人的年齡的公式是相同的。因此可以用一個(gè)函數(shù)來(lái)表示上述關(guān)系，下圖表示求第5個(gè)人年齡的過(guò)程。第7頁(yè)，共33頁(yè)，2023年，2月20日，星期三age(5)age(5)=age(4)+2=18

age(4)age(4)=age(3)+2=16age(3)age(3)=age(2)+2=14age(2)age(2)=age(1)+2=12age(1)=10

回推遞推第8頁(yè)，共33頁(yè)，2023年，2月20日，星期三

從圖可知，求解可分成兩個(gè)階段：第一階段是“回推”，即將第n個(gè)人的年齡表示為第（n-1）個(gè)人年齡的函數(shù)，而第（n一1）個(gè)人的年齡仍然不知道，還要“回推”到第（n一2）個(gè)人的齡……，直到第1個(gè)人的年齡。此時(shí)age(1)已知，不必再向前推了。然后開(kāi)始第二階段，采用遞推方法，從第1個(gè)人的已知年齡推算出第2個(gè)人的年齡（12歲），從第2個(gè)人的年齡推算出3個(gè)人的年齡（14歲）……，一直推算出第5個(gè)人的年齡（18歲）為止。也就是說(shuō)，一個(gè)遞歸的題可以分為“回推”和“遞推”兩個(gè)階段。要經(jīng)歷許多步才能求出最后的值。顯而易見(jiàn)，如果求遞歸過(guò)程不是無(wú)限制進(jìn)行下去，必須具有一個(gè)結(jié)束遞歸過(guò)程的條件。例如，age（1）＝10，就是遞歸結(jié)束的條件。

第9頁(yè)，共33頁(yè)，2023年，2月20日，星期三

可以用一個(gè)函數(shù)來(lái)描述上述遞歸過(guò)程：age（n）/*求年齡的遞歸函數(shù)*／intn；｛intc；／*c用來(lái)存放函數(shù)的返回值if（n==1）c=10;elsec=age（n一1）十2；return（c)；}main（）/*主函數(shù)*／{printf（"%d"，age（5））；}第10頁(yè)，共33頁(yè)，2023年，2月20日，星期三例題二用遞歸方法求n!分析：假設(shè)n=5我們知道

5！=1*2*3*4*5=4！*54！=1*2*3*4=3！*43！=1*2*3=2！*32！=1*2=1！*21！=1可用下面的遞歸公式表示

n!=1（n=1）

n!=(n-1)!*n(n>1)第11頁(yè)，共33頁(yè)，2023年，2月20日，星期三“回推”和“遞推”5！5×4！4×3！3×2！2×1！15！4！×53！×42！×31！×21回推過(guò)程返回1返回1！×2＝2返回2！×3＝6返回3！×4＝24返回4！×5＝120終值120遞推過(guò)程調(diào)用函數(shù)函數(shù)返回值第12頁(yè)，共33頁(yè)，2023年，2月20日，星期三遞歸法求Fibonacci數(shù)列Fibonacci數(shù)列:1,1,2,3,5,8,13…迭代法求Fibonacci數(shù)列的前20項(xiàng)#include<stdio.h>voidmain(){inti,f1=1,f2=1,f3;printf(“%8d%8d”,f1,f2);

for(i=3;i<=20;i++){f3=f1+f2;f1=f2;f2=f3;printf(“%8d”,f3);

if(i%4==0)putchar(‘\n’);}

}迭代法在已知數(shù)列前2項(xiàng)的基礎(chǔ)上,從第3項(xiàng)開(kāi)始,依次向后計(jì)算,得出數(shù)列的每一項(xiàng)第13頁(yè)，共33頁(yè)，2023年，2月20日，星期三

定義Fibonacci數(shù)列的遞歸數(shù)學(xué)模型：遞歸法求Fibonacci數(shù)列1n=0,1F(n-1)+F(n-2)n>1

F(n)=遞歸的終止條件遞歸公式intFib(intn){if(n<0){printf(“error!”);exit(-1);}else

if(n<=1)return1;elsereturnFib(n-1)+Fib(n-2);}遞歸法求Fibonacci數(shù)列第14頁(yè)，共33頁(yè)，2023年，2月20日，星期三用遞歸法求Fibonacci數(shù)列Fib(4)return+Fib(3)Fib(2)return+Fib(1)Fib(0)return+Fib(2)Fib(1)return+Fib(1)Fib(0)return1return1return1return1return1遞歸法是從第n項(xiàng)開(kāi)始向前計(jì)算,當(dāng)n等于0或1時(shí)結(jié)束遞歸調(diào)用,開(kāi)始返回112111235n=20時(shí),要進(jìn)行21891次遞歸調(diào)用思考:求Fibonacci數(shù)列的迭代法和遞歸法誰(shuí)好？遞歸法求Fibonacci數(shù)列第15頁(yè)，共33頁(yè)，2023年，2月20日，星期三5.2Hanoi（漢諾）塔問(wèn)題例5-4編程求解Hanoi（漢諾）塔問(wèn)題。古代有一個(gè)梵塔，塔內(nèi)有三個(gè)柱子A、B、C，僧侶們想把A拄子上的一摞盤(pán)子移動(dòng)到C柱子上。最初A拄子上有大小不等的64個(gè)盤(pán)子，且小的在上，大的在下。在移動(dòng)過(guò)程中，大盤(pán)子只能在下，小盤(pán)子只能在上，并且每次只能移動(dòng)一個(gè)盤(pán)子，可以借助于B柱子。6463621ABC3/4/202316《解析C程序設(shè)計(jì)》第5章模塊化程序設(shè)計(jì)第16頁(yè)，共33頁(yè)，2023年，2月20日，星期三討論：漢諾塔問(wèn)題屬于非數(shù)值問(wèn)題，難以用數(shù)學(xué)公式表達(dá)其算法，可以從分析問(wèn)題本身的規(guī)律入手。第一步，問(wèn)題化簡(jiǎn)，設(shè)A針上只有一個(gè)盤(pán)子，即n=1，則只需將1號(hào)盤(pán)從A針移到C針。第二步，問(wèn)題分解，對(duì)于有n（n>1）個(gè)盤(pán)子的漢諾塔，可分為三個(gè)步驟求解：第17頁(yè)，共33頁(yè)，2023年，2月20日，星期三1.將A針上n-1個(gè)盤(pán)子借助于C針移到B針

2.把A針上剩下的一個(gè)盤(pán)子移到C針

3.將B針上n-1個(gè)盤(pán)子借助于A(yíng)針移到C針顯然，上述1,3兩步具有與原問(wèn)題相同的性質(zhì)，只是在問(wèn)題的規(guī)模上比原問(wèn)題有所縮小，可用遞歸實(shí)現(xiàn)。整理上述分析結(jié)果，把第一步作為遞歸結(jié)束條件，將第二步分析得到的算法作為遞歸算法，可以寫(xiě)出如下完整的遞歸算法描述：定義一個(gè)函數(shù)movedisk(intn,charfromneedle,chartempneedle,chartoneedle)，該函數(shù)的功能是將fromneedle針上的n個(gè)盤(pán)子借助于tempneedle針移動(dòng)到toneedlee針，這樣移動(dòng)n個(gè)盤(pán)子的遞歸算法描述如下：

第18頁(yè)，共33頁(yè)，2023年，2月20日，星期三movedisk(intn,charfromneedle,chartempneedle,chartoneedle){if(n==1)將n號(hào)盤(pán)子從one針移到three針;esle1.movedisk(n-1,fromneedle,toneedle,tempneedle)2.將n號(hào)盤(pán)子從fromneedle針移到toneedle針;3.movedisk(n-1,tempneedle,fromneedle,toneedle)}

按照上述算法可編寫(xiě)出如下C語(yǔ)言程序：第19頁(yè)，共33頁(yè)，2023年，2月20日，星期三#include<stdio.h>voidmain(){voidmovedisk(intn,charfromneedle,chartempneedle,chartoneedle);intn;printf(“Pleasesinputthenumberofdiskes:”);scanf(“%d”,&n);printf(“Thestepmovingdiskesis:\n”);movedisk(n,’A’,’B’,’C’);}voidmovedisk(intn,charfromneedle,chartempneedle,chartoneedle){if(n==1)printf(“%c%c\n”,fromneedle,toneedle);else{movedisk(n-1,fromneedle,toneedle,tempneedle);printf(“%c%c\n”,fromneedle,toneedle);movedisk(n-1,tempneedle,fromneedle,toneedle);}}第20頁(yè)，共33頁(yè)，2023年，2月20日，星期三以N=3為例BCA第21頁(yè)，共33頁(yè)，2023年，2月20日，星期三以N=3為例第一步：A－－＞CBCA第22頁(yè)，共33頁(yè)，2023年，2月20日，星期三以N=3為例第二步：A－－＞BBCA第23頁(yè)，共33頁(yè)，2023年，2月20日，星期三以N=3為例第三步：C－－＞BBCA第24頁(yè)，共33頁(yè)，2023年，2月20日，星期三以N=3為例第四步：A－－＞CBCA第25頁(yè)，共33頁(yè)，2023年，2月20日，星期三以N=3為例第五步：B－－＞ABCA第26頁(yè)，共33頁(yè)，2023年，2月20日，星期三以N=3為例第六步：B－－＞CBCA第27頁(yè)，共33頁(yè)，2023年，2月20日，星期三以N=3為例第七步：A－－＞CBCA第28頁(yè)，共33頁(yè)，2023年，2月20日，星期三第29頁(yè)，共33頁(yè)，2023年，2月20日，星期三八皇后問(wèn)題問(wèn)題描述：會(huì)下國(guó)際象棋的人都很清楚：皇后可以在橫豎斜線(xiàn)上不限步數(shù)地吃掉其他棋子，如何將8個(gè)皇后放在棋盤(pán)上（有8*8個(gè)方格），使他們誰(shuí)也不能被吃掉！這就是著名的八皇后問(wèn)題。對(duì)于某個(gè)滿(mǎn)足要求的8皇后的擺放方法，定義一個(gè)皇后串a(chǎn)與之對(duì)應(yīng)，即a=b1b2…b8，其中bi為相應(yīng)擺法中第i行皇后所處的列數(shù)。已經(jīng)知道8皇后問(wèn)題一共有92組解（即92個(gè)、不同的皇后串）。給出一個(gè)數(shù)b，要求輸出第b個(gè)串。串的比較是這樣的：皇后串x置于皇后串y之前，當(dāng)且僅當(dāng)將x視為整數(shù)時(shí)比y小。輸入數(shù)據(jù)：第一行是測(cè)試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入，每組測(cè)試數(shù)據(jù)占1行，包括一個(gè)正整數(shù)b（1<=b<=92）。輸出要求：n行，每行輸出對(duì)應(yīng)一個(gè)輸入。輸出應(yīng)是一個(gè)正整數(shù)，是對(duì)應(yīng)于b的皇后串。輸入樣例：2192輸出樣例：15863724第30頁(yè)，共33頁(yè)，2023年，2月20日，星期三解題思路：1、因?yàn)橐蟪?2中不同的擺放方法中的任意一種，所有我們不妨把92中不同的擺放方法一次性求出來(lái)，存放在一個(gè)數(shù)組里。為求解這道題我們需要一個(gè)矩陣仿真棋盤(pán)，每次試放一個(gè)棋子時(shí)只能放在尚未被控制的格子上，一旦放置了一個(gè)新棋子，就在它所能控制的所有位置上設(shè)置標(biāo)記，如此下去把八個(gè)棋子放好。完成一種擺放時(shí)，就要嘗試下一種。若要按照字典序?qū)⒖尚袛[放方法記錄下來(lái)，就要按照一定的順序進(jìn)行嘗試。也就是將第一個(gè)棋子按照從小到大的順序嘗試，對(duì)于第一個(gè)棋子的位置，將第二個(gè)棋子從可行的位置從小到大的順序嘗試；在第一和第二個(gè)棋子固定的情況下，將第三個(gè)棋子從可行的位置從小到大的順序嘗試；以此類(lèi)