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

1、,函數(shù)的遞歸調(diào)用,函數(shù)的遞歸調(diào)用 遞歸: 一個函數(shù)直接或間接地使用自身。 1. 直接遞歸調(diào)用：函數(shù)直接調(diào)用本身 2. 間接遞歸調(diào)用：函數(shù)間接調(diào)用本身,情景1：,小時候，我們聽過這樣的故事： 從前有座山，山上有座廟，廟里有個老和尚給小和尚講故事，講的什么故事呢？從前有座山，山上有座廟，廟里有個老和尚給小和尚講故事，講的什么故事呢？從前有座山，山上有座廟，廟里有個老和尚給小和尚講故事，講的什么故事呢？,故事可以一直講下去，每一個故事內(nèi)容都相同，但卻是故事里的故事。,程序設(shè)計中，函數(shù)A自己調(diào)用自己，稱為直接遞歸調(diào)用。,情景2：,鏡子A和鏡子B相對放在一起，你會發(fā)現(xiàn)什么現(xiàn)象呢？,對了，我們會發(fā)現(xiàn)鏡子A

2、中有鏡子B的映象，鏡子B中又鏡子A的映象，這樣層層疊疊，無窮無盡。,A,B,在程序設(shè)計中，像這種函數(shù)A調(diào)用函數(shù)B,函數(shù)B再反過來調(diào)用函數(shù)A的算法，稱為間接遞歸調(diào)用。,遞歸算法的特點： 遞歸函數(shù)的執(zhí)行過程比較復(fù)雜，往往都存在著連續(xù)的遞歸調(diào)用，其執(zhí)行過程可分為 “遞推” 和 “回歸” 兩個階段，先是一次一次不斷的遞推過程，直到符合遞推”結(jié)束條件，然后是一層一層的回歸過程。 而其中的每一次遞歸調(diào)用，系統(tǒng)都要在棧中分配空間以保存該次調(diào)用的返回地址、 參數(shù)、局部變量，因此在遞推階段，?？臻g一直處于增長狀態(tài)， 然后進入回歸階段，?？臻g反向依次釋放。 直到“遞推” 過程的終止， 在遞歸的執(zhí)行過程中，遞歸結(jié)束

3、條件非常重要，它控制 “遞推” 過程的終止，在任何一個遞歸函數(shù)中，遞歸結(jié)束條件都是必不可少的， 否則將會一直 “遞推” 下去。導(dǎo)致無窮遞歸。 遞歸算法的缺點：內(nèi)存消耗巨大，且連續(xù)地調(diào)用和返回操作占用較多的CPU時間。 遞歸算法的優(yōu)點：算法描述簡潔易懂。,思考如下問題：,例1: 有5個人坐在一起,問第5個人多少歲, 他說比第4個人大2歲;問第4個人歲數(shù),他說比 第3個人大2歲;問第3個人,又說比第2個大2歲; 問第2個人，說比第1個人大2歲；最后問第1 個人，他說他10歲；請問第5個人多大?,比她大2歲,比她大2歲,比她大2歲,比她大2歲,我10歲,分析：要求第5個人的年齡，就必須先知道第4個人

4、的年齡，而第4個人的年齡也不知道，要求第4個人的年齡必須先知道第3個人的年齡，而第3個人的年齡又取決于第2個人的年齡，第2個人的年齡取決于第1個人的年齡。而且每一個人的年齡都比其前1個人的年齡大2。第一個人的年齡已知，根據(jù)第一個人的年齡可依次求得第二、三、四、五個人的年齡。這就是一個遞歸問題。 而每一個人的年齡都比其前1個人的年齡大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

5、)+2 （n1） 可以看到，當n1時，求第n個人的年齡的公式是相同的。因此可以用一個函數(shù)來表示上述關(guān)系，下圖表示求第5個人年齡的過程。,age(5) age(5) =age(4)+2 =18 age(4) age(4) =age(3)+2 =16 age(3) age(3) =age(2)+2 =14 age(2) age(2) =age(1)+2 = 12 age(1) =10,回推,遞推,從圖可知，求解可分成兩個階段：第一階段是“回推”，即將第n個人的年齡表示為第（n-1）個人年齡的函數(shù)，而第（n一1）個人的年齡仍然不知道，還要“回推”到第（n一2）個人的齡，直到第1個人的年齡。此時age

6、(1)已知，不必再向前推了。然后開始第二階段，采用遞推方法，從第1個人的已知年齡推算出第2個人的年齡（12歲），從第2個人的年齡推算出3個人的年齡（14歲），一直推算出第5個人的年齡（18歲）為止。也就是說，一個遞歸的題可以分為“回推”和“遞推”兩個階段。要經(jīng)歷許多步才能求出最后的值。顯而易見，如果求遞歸過程不是無限制進行下去，必須具有一個結(jié)束遞歸過程的條件。 例如，age（1）10，就是遞歸結(jié)束的條件。,可以用一個函數(shù)來描述上述遞歸過程： age（n） /*求年齡的遞歸函數(shù)* int n； int c； * c用來存放函數(shù)的返回值 if（n= =1） c=10; else c=age（n一1

7、）十2； return（c)； main（）/*主函數(shù)* printf（%d，age（5）；,例題二 用遞歸方法求n! 分析：假設(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),“回推”和“遞推”,遞歸法求Fibonacci數(shù)列 Fibonacci數(shù)列: 1, 1, 2, 3, 5, 8, 13 迭代法求Fibonacci數(shù)列的前20項 #include void main( ) int i , f1=1 , f2

8、=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項的基礎(chǔ)上, 從第3項開始, 依次向后計算, 得出數(shù)列的每一項,定義Fibonacci數(shù)列的遞歸數(shù)學(xué)模型：,遞歸法求Fibonacci數(shù)列,遞歸的終止條件,遞歸公式,int Fib(int n) if (n0) printf(“error!”); exit(-1); else if (n = 1) return 1; el

9、se return Fib(n-1)+Fib(n-2); ,遞歸法求Fibonacci數(shù)列,用遞歸法求Fibonacci數(shù)列,Fib(4),return 1,遞歸法是從第n項開始向前計算, 當n等于0或1時結(jié)束遞歸調(diào)用,開始返回,n=20時, 要進行21891次遞歸調(diào)用,思考: 求Fibonacci數(shù)列的迭代法和遞歸法誰好？,遞歸法求Fibonacci數(shù)列,16,5.2 Hanoi（漢諾）塔問題,例5-4 編程求解Hanoi（漢諾）塔問題。 古代有一個梵塔，塔內(nèi)有三個柱子A、B、C，僧侶們想把A拄子上的一摞盤子移動到C柱子上。最初A拄子上有大小不等的64個盤子，且小的在上，大的在下。在移動過程

10、中，大盤子只能在下，小盤子只能在上，并且每次只能移動一個盤子，可以借助于B柱子。,討論：漢諾塔問題屬于非數(shù)值問題，難以用數(shù)學(xué)公式表達其算法，可以從分析問題本身的規(guī)律入手。 第一步，問題化簡，設(shè)A針上只有一個盤子，即n=1，則只需將1號盤從A針移到C針。 第二步，問題分解，對于有n（n1）個盤子的漢諾塔，可分為三個步驟求解：,1.將A針上n-1個盤子借助于C針移到B針 2.把A針上剩下的一個盤子移到C針 3.將B針上n-1個盤子借助于A針移到C針 顯然，上述1,3兩步具有與原問題相同的性質(zhì)，只是在問題的規(guī)模上比原問題有所縮小，可用遞歸實現(xiàn)。 整理上述分析結(jié)果，把第一步作為遞歸結(jié)束條件，將第二步分

11、析得到的算法作為遞歸算法，可以寫出如下完整的遞歸算法描述： 定義一個函數(shù)movedisk (int n,char fromneedle ,char tempneedle , char toneedle )，該函數(shù)的功能是將fromneedle針上的n個盤子借助于tempneedle針移動到toneedlee針，這樣移動n個盤子的遞歸算法描述如下：,movedisk(int n,char fromneedle,char tempneedle,char toneedle) if (n=1) 將n號盤子從one針移到three針; esle 1. movedisk(n-1 , fromneedle

12、, toneedle , tempneedle) 2.將n號盤子從fromneedle針移到toneedle針; 3. movedisk(n-1, tempneedle, fromneedle, toneedle) 按照上述算法可編寫出如下C語言程序：,#include void main() void movedisk(int n,char fromneedle,char tempneedle,char toneedle); int n; printf (“Pleases input the number of diskes:”); scanf(“%d”, ,以N=3為例,以N=3為例,第一

13、步：A C,以N=3為例,第二步：A B,以N=3為例,第三步：CB,以N=3為例,第四步：AC,以N=3為例,第五步：BA,以N=3為例,第六步：BC,以N=3為例,第七步：AC,八皇后問題,問題描述： 會下國際象棋的人都很清楚：皇后可以在橫豎斜線上不限步數(shù)地吃掉其他棋子，如何將8個皇后放在棋盤上（有8*8個方格），使他們誰也不能被吃掉！這就是著名的八皇后問題。對于某個滿足要求的8皇后的擺放方法，定義一個皇后串a(chǎn)與之對應(yīng)，即a=b1b2b8，其中bi為相應(yīng)擺法中第i行皇后所處的列數(shù)。已經(jīng)知道8皇后問題一共有92組解（即92個、不同的皇后串）。給出一個數(shù)b，要求輸出第b個串。串的比較是這樣的：

14、皇后串x置于皇后串y之前，當且僅當將x視為整數(shù)時比y小。 輸入數(shù)據(jù)： 第一行是測試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入，每組測試數(shù)據(jù)占1行，包括一個正整數(shù)b（1=b=92）。 輸出要求： n行，每行輸出對應(yīng)一個輸入。輸出應(yīng)是一個正整數(shù)，是對應(yīng)于b的皇后串。 輸入樣例： 2 1 92 輸出樣例： 15863724,解題思路： 1、因為要求出92中不同的擺放方法中的任意一種，所有我們不妨把92中不同的擺放方法一次性求出來，存放在一個數(shù)組里。為求解這道題我們需要一個矩陣仿真棋盤，每次試放一個棋子時只能放在尚未被控制的格子上，一旦放置了一個新棋子，就在它所能控制的所有位置上設(shè)置標記，如此下去把八個棋子放好。

15、完成一種擺放時，就要嘗試下一種。若要按照字典序?qū)⒖尚袛[放方法記錄下來，就要按照一定的順序進行嘗試。也就是將第一個棋子按照從小到大的順序嘗試，對于第一個棋子的位置，將第二個棋子從可行的位置從小到大的順序嘗試；在第一和第二個棋子固定的情況下，將第三個棋子從可行的位置從小到大的順序嘗試；以此類推。 2、首先，我們有一個8*8的矩陣仿真棋盤標識當前已經(jīng)擺好的棋子所控制的區(qū)域。用一個92行每行8個元素的二維數(shù)組記錄可行的擺放方法。用一個遞歸程序?qū)崿F(xiàn)嘗試擺放的過程?；舅枷刖褪羌僭O(shè)我們將第一個棋子擺好，并設(shè)置它的控制區(qū)域，則這個問題就變成了一個7皇后問題，用與8皇后同樣的方法可以獲得問題的求解。那我們就把

16、重心放在如何擺放一個皇后棋子上，擺放的基本步驟是：從第1到第8個位置，順序地嘗試將棋子放置在每一個未被控制的位置，設(shè)置該棋子所控制的格子，將問題變成更小規(guī)模的問題向下遞歸，需要注意的是每次嘗試一個新的未被控制的位置前，要將上一次嘗試的位置所控制的格子復(fù)原。,#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+) queenPlacesji=0; putQueen(0);/從第0個棋子開始擺放 scanf(“%d”, ,void putQueen(int ithQueen) int i,k,r; i