VB函數(shù)遞歸與調(diào)用PPT精選文檔

1、1 函數(shù)的遞歸調(diào)用 2 函數(shù)的遞歸調(diào)用 遞歸遞歸: 一個(gè)函數(shù)直接或間接地使用自身。一個(gè)函數(shù)直接或間接地使用自身。 1. 直接遞歸調(diào)用：直接遞歸調(diào)用：函數(shù)直接調(diào)用本身函數(shù)直接調(diào)用本身 2. 間接遞歸調(diào)用：間接遞歸調(diào)用：函數(shù)間接調(diào)用本身函數(shù)間接調(diào)用本身3情景情景1：小時(shí)候，我們聽過這樣的故事：小時(shí)候，我們聽過這樣的故事：從前有座山，山上有座廟，廟里有個(gè)老和尚給小和尚講故從前有座山，山上有座廟，廟里有個(gè)老和尚給小和尚講故事，講的什么事，講的什么故事故事呢？呢？從前有座山，山上有座廟，廟里有從前有座山，山上有座廟，廟里有個(gè)老和尚給小和尚講故事，講的什么個(gè)老和尚給小和尚講故事，講的什么故事故事呢？呢？從

2、前有座山，從前有座山，山上有座廟，廟里有個(gè)老和尚給小和尚講故事，講的什么山上有座廟，廟里有個(gè)老和尚給小和尚講故事，講的什么故事呢？故事呢？故事可以一直講下去，每一個(gè)故事內(nèi)容都相同，但卻是故事里的故事。程序設(shè)計(jì)中，函數(shù)A自己調(diào)用自己，稱為直接直接遞歸調(diào)用遞歸調(diào)用。4情景情景2：鏡子鏡子A和鏡子和鏡子B相對(duì)放在一起，你會(huì)發(fā)現(xiàn)什么相對(duì)放在一起，你會(huì)發(fā)現(xiàn)什么現(xiàn)象呢？現(xiàn)象呢？對(duì)了，我們會(huì)發(fā)現(xiàn)鏡子對(duì)了，我們會(huì)發(fā)現(xiàn)鏡子A A中有鏡子中有鏡子B B的映象，鏡的映象，鏡子子B B中又鏡子中又鏡子A A的映象，的映象，這樣層層疊疊，無窮無這樣層層疊疊，無窮無盡。盡。AB在程序設(shè)計(jì)中，像這種函數(shù)A調(diào)用函數(shù)B,函數(shù)B

3、再反過來調(diào)用函數(shù)A的算法，稱為間接間接遞歸調(diào)用遞歸調(diào)用。5 遞歸算法的特點(diǎn)：遞歸函數(shù)的執(zhí)行過程比較復(fù)雜，往往都存在著連續(xù)的遞歸調(diào)用，其執(zhí)行過程可分為 “遞推” 和 “回歸” 兩個(gè)階段，先是一次一次不斷的遞推過程，直到符合遞推”結(jié)束條件，然后是一層一層的回歸過程。 而其中的每一次遞歸調(diào)用，系統(tǒng)都要在棧中分配空間以保存該次調(diào)用的返回地址、 參數(shù)、局部變量，因此在遞推階段，?？臻g一直處于增長(zhǎng)狀態(tài)， 然后進(jìn)入回歸階段，?？臻g反向依次釋放。 直到“遞推” 過程的終止， 在遞歸的執(zhí)行過程中，遞歸結(jié)束條件非常重要，它控制 “遞推” 過程的終止，在任何一個(gè)遞歸函數(shù)中，遞歸結(jié)束條件都是必不可少的， 否則將會(huì)一直

4、 “遞推” 下去。導(dǎo)致無窮遞歸。遞歸算法的缺點(diǎn)：內(nèi)存消耗巨大，且連續(xù)地調(diào)用和返回操作占用較多的CPU時(shí)間。 遞歸算法的優(yōu)點(diǎn)：算法描述簡(jiǎn)潔易懂。6 思考如下問題：思考如下問題：例例1: 有有5個(gè)人坐在一起個(gè)人坐在一起,問第問第5個(gè)人多少歲個(gè)人多少歲,他說比第他說比第4個(gè)人大個(gè)人大2歲歲;問第問第4個(gè)人歲數(shù)個(gè)人歲數(shù),他說比他說比第第3個(gè)人大個(gè)人大2歲歲;問第問第3個(gè)人個(gè)人,又說比第又說比第2個(gè)大個(gè)大2歲歲;問第問第2個(gè)人，說比第個(gè)人，說比第1個(gè)人大個(gè)人大2歲；最后問第歲；最后問第1個(gè)人，他說他個(gè)人，他說他10歲；請(qǐng)問第歲；請(qǐng)問第5個(gè)人多大個(gè)人多大?比她大比她大2歲歲比她大比她大2歲歲比她大比她大2

5、歲歲比她大比她大2歲歲我我10歲歲7分析分析：要求第：要求第5個(gè)人的年齡，就必須先知道第個(gè)人的年齡，就必須先知道第4個(gè)人的年齡，而第個(gè)人的年齡，而第4個(gè)人個(gè)人的年齡也不知道，要求第的年齡也不知道，要求第4個(gè)人的年齡必須先知道第個(gè)人的年齡必須先知道第3個(gè)人的年齡，而個(gè)人的年齡，而第第3個(gè)人的年齡又取決于第個(gè)人的年齡又取決于第2個(gè)人的年齡，第個(gè)人的年齡，第2個(gè)人的年齡取決于第個(gè)人的年齡取決于第1個(gè)人的年齡。而且每一個(gè)人的年齡都比其前個(gè)人的年齡。而且每一個(gè)人的年齡都比其前1個(gè)人的年齡大個(gè)人的年齡大2。第一個(gè)。第一個(gè)人的年齡已知，根據(jù)第一個(gè)人的年齡可依次求得第二、三、四、五個(gè)人的年齡已知，根據(jù)第一個(gè)人

6、的年齡可依次求得第二、三、四、五個(gè)人的年齡。這就是一個(gè)遞歸問題。人的年齡。這就是一個(gè)遞歸問題。而而每一個(gè)人的年齡都比其前每一個(gè)人的年齡都比其前1個(gè)人的年齡大個(gè)人的年齡大2 就是遞歸成立的條件，也就就是遞歸成立的條件，也就是是遞歸公式遞歸公式。age（5）=age（4）2 age（4）=age（3）2 age（3）=age (2）+2 age（2）age(1）2 age（1）10 可以用式子表述如下：可以用式子表述如下： age（n）=10 （n=1） age（n）= age（n-1)+2 （n1）可以看到，當(dāng)可以看到，當(dāng)n1時(shí)，求第時(shí)，求第n個(gè)人的年齡的公式是相同的。因此可以用個(gè)人的年齡的公式

7、是相同的。因此可以用一個(gè)函數(shù)來表示上述關(guān)系，下圖表示求第一個(gè)函數(shù)來表示上述關(guān)系，下圖表示求第5個(gè)人年齡的過程。個(gè)人年齡的過程。8回推回推遞推遞推91011 例題二例題二 用遞歸方法求用遞歸方法求n! 分析：假設(shè)分析：假設(shè)n=5 我們知道我們知道 5！=1*2*3*4*5=4！*5 4！=1*2*3*4=3！*4 3！=1*2*3=2！*3 2！=1*2=1！*2 1！=1 可用下面的遞歸公式表示可用下面的遞歸公式表示 n!=1 （n=1） n!=(n-1)!*n (n 1)12“回推”和“遞推”5！54！43！32！21！15！4！53！42！31！21回推過程返回1返回1！22返回2！36返

8、回3！424返回4！5120終值120遞推過程調(diào)用函數(shù)函數(shù)返回值13 遞歸法求遞歸法求Fibonacci數(shù)列數(shù)列 Fibonacci數(shù)列數(shù)列: 1, 1, 2, 3, 5, 8, 13 迭代法求迭代法求Fibonacci數(shù)列的前數(shù)列的前20項(xiàng)項(xiàng) #include void main( ) int i , f1=1 , f2=1 , f3; printf(“%8d%8d”, f1 , f2); for ( i=3 ; i1 F(n)=遞歸的終止條件遞歸的終止條件遞歸公式遞歸公式int Fib(int n) if (n0) printf(“error!”); exit(-1); else if (

9、n 1）個(gè)盤子的漢諾塔，可分為三個(gè)步驟求解：181.將A針上n-1個(gè)盤子借助于C針移到B針 2.把A針上剩下的一個(gè)盤子移到C針 3.將B針上n-1個(gè)盤子借助于A針移到C針 顯然，上述1,3兩步具有與原問題相同的性質(zhì)，只是在問題的規(guī)模上比原問題有所縮小，可用遞歸實(shí)現(xiàn)。 整理上述分析結(jié)果，把第一步作為遞歸結(jié)束條件，將第二步分析得到的算法作為遞歸算法，可以寫出如下完整的遞歸算法描述： 定義一個(gè)函數(shù)movedisk (int n,char fromneedle ,char tempneedle , char toneedle )，該函數(shù)的功能是將fromneedle針上的n個(gè)盤子借助于tempneed

10、le針移動(dòng)到toneedlee針，這樣移動(dòng)n個(gè)盤子的遞歸算法描述如下： 19movedisk(int n,char fromneedle,char tempneedle,char toneedle) if (n=1) 將n號(hào)盤子從one針移到three針; esle 1. movedisk(n-1 , fromneedle , toneedle , tempneedle) 2.將n號(hào)盤子從fromneedle針移到toneedle針; 3. movedisk(n-1, tempneedle, fromneedle, toneedle) 按照上述算法可編寫出如下C語(yǔ)言程序： 20#include

11、 void main() void movedisk(int n,char fromneedle,char tempneedle,char toneedle); int n; printf (“Pleases input the number of diskes:”); scanf(“%d”,&n); printf (“The step moving diskes is:n”); movedisk (n,A,B,C); void movedisk(int n,char fromneedle,char tempneedle,char toneedle) if (n=1) printf (

12、“%c%cn”,fromneedle,toneedle ); else movedisk(n-1,fromneedle,toneedle,tempneedle ); printf (“%c%cn”,fromneedle,toneedle ); movedisk (n-1,tempneedle,fromneedle,toneedle ); 21以N=3為例BCA22以N=3為例 第一步：A CBCA23以N=3為例 第二步：A BBCA24以N=3為例 第三步：CBBCA25以N=3為例 第四步：ACBCA26以N=3為例 第五步：BABCA27以N=3為例 第六步：BCBCA28以N=3為例

13、第七步：ACBCA2930八皇后問題問題描述：?jiǎn)栴}描述： 會(huì)下國(guó)際象棋的人都很清楚：皇后可以在橫豎斜線上不限步數(shù)地吃掉其會(huì)下國(guó)際象棋的人都很清楚：皇后可以在橫豎斜線上不限步數(shù)地吃掉其他棋子，如何將他棋子，如何將8 8個(gè)皇后放在棋盤上（有個(gè)皇后放在棋盤上（有8 8* *8 8個(gè)方格），使他們誰也不能個(gè)方格），使他們誰也不能被吃掉！這就是著名的八皇后問題。對(duì)于某個(gè)滿足要求的被吃掉！這就是著名的八皇后問題。對(duì)于某個(gè)滿足要求的8 8皇后的擺放方皇后的擺放方法，定義一個(gè)皇后串法，定義一個(gè)皇后串a(chǎn) a與之對(duì)應(yīng)，即與之對(duì)應(yīng)，即a=b1b2a=b1b2b8b8，其中，其中bibi為相應(yīng)擺法中第為相應(yīng)擺法中第i

14、 i行皇后所處的列數(shù)。已經(jīng)知道行皇后所處的列數(shù)。已經(jīng)知道8 8皇后問題一共有皇后問題一共有9292組解（即組解（即9292個(gè)、不同個(gè)、不同的皇后串）。給出一個(gè)數(shù)的皇后串）。給出一個(gè)數(shù)b b，要求輸出第，要求輸出第b b個(gè)串。串的比較是這樣的：皇個(gè)串。串的比較是這樣的：皇后串后串x x置于皇后串置于皇后串y y之前，當(dāng)且僅當(dāng)將之前，當(dāng)且僅當(dāng)將x x視為整數(shù)時(shí)比視為整數(shù)時(shí)比y y小。小。輸入數(shù)據(jù)：輸入數(shù)據(jù)： 第一行是測(cè)試數(shù)據(jù)的組數(shù)第一行是測(cè)試數(shù)據(jù)的組數(shù)n n，后面跟著，后面跟著n n行輸入，每組測(cè)試數(shù)據(jù)占行輸入，每組測(cè)試數(shù)據(jù)占1 1行，包行，包括一個(gè)正整數(shù)括一個(gè)正整數(shù)b b（1=b=921=b=9

15、2）。）。輸出要求：輸出要求：n n行，每行輸出對(duì)應(yīng)一個(gè)輸入。輸出應(yīng)是一個(gè)正整數(shù)，是對(duì)應(yīng)于行，每行輸出對(duì)應(yīng)一個(gè)輸入。輸出應(yīng)是一個(gè)正整數(shù)，是對(duì)應(yīng)于b b的皇后串。的皇后串。輸入樣例：輸入樣例：2 21 19292輸出樣例：輸出樣例：158637241586372431解題思路：解題思路：1 1、因?yàn)橐蟪觥⒁驗(yàn)橐蟪?292中不同的擺放方法中的任意一種，所有我們不妨把中不同的擺放方法中的任意一種，所有我們不妨把9292中不同的中不同的擺放方法一次性求出來，存放在一個(gè)數(shù)組里。為求解這道題我們需要一個(gè)矩?cái)[放方法一次性求出來，存放在一個(gè)數(shù)組里。為求解這道題我們需要一個(gè)矩陣仿真棋盤，每次試放一個(gè)棋子時(shí)只

16、能放在尚未被控制的格子上，一旦放置陣仿真棋盤，每次試放一個(gè)棋子時(shí)只能放在尚未被控制的格子上，一旦放置了一個(gè)新棋子，就在它所能控制的所有位置上設(shè)置標(biāo)記，如此下去把八個(gè)棋了一個(gè)新棋子，就在它所能控制的所有位置上設(shè)置標(biāo)記，如此下去把八個(gè)棋子放好。完成一種擺放時(shí)，就要嘗試下一種。若要按照字典序?qū)⒖尚袛[放方子放好。完成一種擺放時(shí)，就要嘗試下一種。若要按照字典序?qū)⒖尚袛[放方法記錄下來，就要按照一定的順序進(jìn)行嘗試。也就是將第一個(gè)棋子按照從小法記錄下來，就要按照一定的順序進(jìn)行嘗試。也就是將第一個(gè)棋子按照從小到大的順序嘗試，對(duì)于第一個(gè)棋子的位置，將第二個(gè)棋子從可行的位置從小到大的順序嘗試，對(duì)于第一個(gè)棋子的位置，

17、將第二個(gè)棋子從可行的位置從小到大的順序嘗試；在第一和第二個(gè)棋子固定的情況下，將第三個(gè)棋子從可行到大的順序嘗試；在第一和第二個(gè)棋子固定的情況下，將第三個(gè)棋子從可行的位置從小到大的順序嘗試；以此類推。的位置從小到大的順序嘗試；以此類推。2 2、首先，我們有一個(gè)、首先，我們有一個(gè)8 8* *8 8的矩陣仿真棋盤標(biāo)識(shí)當(dāng)前已經(jīng)擺好的棋子所控制的區(qū)域。的矩陣仿真棋盤標(biāo)識(shí)當(dāng)前已經(jīng)擺好的棋子所控制的區(qū)域。用一個(gè)用一個(gè)9292行每行行每行8 8個(gè)元素的二維數(shù)組記錄可行的擺放方法。用一個(gè)遞歸程序?qū)崅€(gè)元素的二維數(shù)組記錄可行的擺放方法。用一個(gè)遞歸程序?qū)崿F(xiàn)嘗試擺放的過程?；舅枷刖褪羌僭O(shè)我們將第一個(gè)棋子擺好，并設(shè)置它的

18、現(xiàn)嘗試擺放的過程?；舅枷刖褪羌僭O(shè)我們將第一個(gè)棋子擺好，并設(shè)置它的控制區(qū)域，則這個(gè)問題就變成了一個(gè)控制區(qū)域，則這個(gè)問題就變成了一個(gè)7 7皇后問題，用與皇后問題，用與8 8皇后同樣的方法可以皇后同樣的方法可以獲得問題的求解。那我們就把重心放在如何擺放一個(gè)皇后棋子上，擺放的基獲得問題的求解。那我們就把重心放在如何擺放一個(gè)皇后棋子上，擺放的基本步驟是：從第本步驟是：從第1 1到第到第8 8個(gè)位置，順序地嘗試將棋子放置在每一個(gè)未被控制的個(gè)位置，順序地嘗試將棋子放置在每一個(gè)未被控制的位置，設(shè)置該棋子所控制的格子，將問題變成更小規(guī)模的問題向下遞歸，需位置，設(shè)置該棋子所控制的格子，將問題變成更小規(guī)模的問題向下遞歸，需要注意的是每次嘗試一個(gè)新的未被控制的位置前，要將上一次嘗試的位置所要注意的是每次嘗試一個(gè)新的未被控制的位置前，要將上一次嘗試的位置所控制的格子復(fù)原?？刂频母褡訌?fù)原。32#include #include int queenPlaces928; int count=0; int board88; void putQueen(int ithQueen);/遞歸函數(shù)void main() int n,i,j; for(i=0;i8;i+) for(j=0;i8;j+) boardij=-1; for(j=0;j92;j