VB函數(shù)遞歸與調(diào)用公開課一等獎省優(yōu)質(zhì)課大賽獲獎?wù)n件

函數(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)象呢？對了，我們會發(fā)覺鏡子A中有鏡子B映象，鏡子B中又鏡子A映象，這么層層疊疊，無窮無盡。AB在程序設(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ù)、局部變量，所以在遞推階段，棧空間一直處于增加狀態(tài)，然后進(jìn)入回歸階段，棧空間反向依次釋放。直到“遞推”過程終止，③在遞歸執(zhí)行過程中，遞歸結(jié)束條件非常主要，它控制“遞推”過程終止，在任何一個遞歸函數(shù)中，遞歸結(jié)束條件都是必不可少，不然將會一直“遞推”下去。造成無窮遞歸。遞歸算法缺點：內(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個人年紀(jì)，就必須先知道第4個人年紀(jì)，而第4個人年紀(jì)也不知道，要求第4個人年紀(jì)必須先知道第3個人年紀(jì)，而第3個人年紀(jì)又取決于第2個人年紀(jì)，第2個人年紀(jì)取決于第1個人年紀(jì)。而且每一個人年紀(jì)都比其前1個人年紀(jì)大2。第一個人年紀(jì)已知，依據(jù)第一個人年紀(jì)可依次求得第二、三、四、五個人年紀(jì)。這就是一個遞歸問題。而每一個人年紀(jì)都比其前1個人年紀(jì)大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時，求第n個人年紀(jì)公式是相同。所以能夠用一個函數(shù)來表示上述關(guān)系，下列圖表示求第5個人年紀(jì)過程。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

回推遞推

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

能夠用一個函數(shù)來描述上述遞歸過程：age（n）/*求年紀(jì)遞歸函數(shù)*／intn；｛intc；／*c用來存放函數(shù)返回值if（n==1）c=10;elsec=age（n一1）十2；return（c)；}main（）/*主函數(shù)*／{printf（"%d"，age（5））；}例題二用遞歸方法求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)“回推”和“遞推”5！5×4！4×3！3×2！2×1！15！4！×53！×42！×31！×21回推過程返回1返回1！×2＝2返回2！×3＝6返回3！×4＝24返回4！×5＝120終值120遞推過程調(diào)用函數(shù)函數(shù)返回值遞歸法求Fibonacci數(shù)列Fibonacci數(shù)列:1,1,2,3,5,8,13…迭代法求Fibonacci數(shù)列前20項#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項基礎(chǔ)上,從第3項開始,依次向后計算,得出數(shù)列每一項

定義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ù)列用遞歸法求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項開始向前計算,當(dāng)n等于0或1時結(jié)束遞歸調(diào)用,開始返回112111235n=20時,要進(jìn)行21891次遞歸調(diào)用思索:求Fibonacci數(shù)列迭代法和遞歸法誰好？遞歸法求Fibonacci數(shù)列16《解析C程序設(shè)計》第5章模塊化程序設(shè)計/10/105.2Hanoi（漢諾）塔問題例5-4編程求解Hanoi（漢諾）塔問題。古代有一個梵塔，塔內(nèi)有三個柱子A、B、C，僧侶們想把A拄子上一摞盤子移動到C柱子上。最初A拄子上有大小不等64個盤子，且小在上，大在下。在移動過程中，大盤子只能在下，小盤子只能在上，而且每次只能移動一個盤子，能夠借助于B柱子。6463621ABC討論：漢諾塔問題屬于非數(shù)值問題，難以用數(shù)學(xué)公式表示其算法，能夠從分析問題本身規(guī)律入手。第一步，問題化簡，設(shè)A針上只有一個盤子，即n=1，則只需將1號盤從A針移到C針。第二步，問題分解，對于有n（n>1）個盤子漢諾塔，可分為三個步驟求解：1.將A針上n-1個盤子借助于C針移到B針

2.把A針上剩下一個盤子移到C針

3.將B針上n-1個盤子借助于A針移到C針顯然，上述1,3兩步含有與原問題相同性質(zhì)，只是在問題規(guī)模上比原問題有所縮小，可用遞歸實現(xiàn)。整理上述分析結(jié)果，把第一步作為遞歸結(jié)束條件，將第二步分析得到算法作為遞歸算法，能夠?qū)懗鲆韵峦暾f歸算法描述：定義一個函數(shù)movedisk(intn,charfromneedle,chartempneedle,chartoneedle)，該函數(shù)功效是將fromneedle針上n個盤子借助于tempneedle針移動到toneedlee針，這么移動n個盤子遞歸算法描述以下：

movedisk(intn,charfromneedle,chartempneedle,chartoneedle){if(n==1)將n號盤子從one針移到three針;esle1.movedisk(n-1,fromneedle,toneedle,tempneedle)2.將n號盤子從fromneedle針移到toneedle針;3.movedisk(n-1,tempneedle,fromneedle,toneedle)}

按照上述算法可編寫出以下C語言程序：#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);}}以N=3為例BCA以N=3為例第一步：A－－＞CBCA以N=3為例第二步：A－－＞BBCA以N=3為例第三步：C－－＞BBCA以N=3為例第四步：A－－＞CBCA以N=3為例第五步：B－－＞ABCA以N=3為例第六步：B－－＞CBCA以N=3為例第七步：A－－＞CBCA八皇后問題問題描述：會下國際象棋人都很清楚：皇后能夠在橫豎斜線上不限步數(shù)地吃掉其它棋子，怎樣將8個皇后放在棋盤上（有8*8個方格），使他們誰也不能被吃掉！這就是著名八皇后問題。對于某個滿足要求8皇后擺放方法，定義一個皇后串a(chǎn)與之對應(yīng)，即a=b1b2…b8，其中bi為對應(yīng)擺法中第i行皇后所處列數(shù)。已經(jīng)知道8皇后問題一共有92組解（即92個、不一樣皇后串）。給出一個數(shù)b，要求輸出第b個串。串比較是這么：皇后串x置于皇后串y之前，當(dāng)且僅當(dāng)將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皇后串。輸入樣例：2192輸出樣例：15863724解題思緒：1、因為要求出92中不一樣擺放方法中任意一個，全部我們不妨把92中不一樣擺放方法一次性求出來，存放在一個數(shù)組里。為求解這道題我們需要一個矩陣仿真棋盤，每次試放一個棋子時只能放在還未被控制格子上，一旦放置了一個新棋子，就在它所能控制全部位置上設(shè)置標(biāo)識，如此下去把八個棋子放好。完成一個擺放時，就要嘗試下一個。若要按照字典序?qū)⒖尚袛[放方法統(tǒng)計下來，就要按照一定次序進(jìn)行嘗試。也就是將第一個棋子按照從小到大次序嘗試，對于第一個棋子位置，將第二個棋子從可行位置從小到大次序嘗試；在第一和第二個棋子固定情況下，將第三個棋子從可行位置從小到大次序嘗試；以這類推。2、首先，我們有一個8*8矩陣仿真棋盤標(biāo)識當(dāng)前已經(jīng)擺好棋子所控制區(qū)域。用一個92行每行8個元素二維數(shù)組統(tǒng)計可行擺放方法。用一個遞歸程序?qū)崿F(xiàn)嘗試擺放過程。基本思想就是假設(shè)我們將第一個棋子擺好，并設(shè)置它控制區(qū)域，則這個問題就變成了一個7皇后問題，用與8皇后一樣方法能夠取得問題求解。那我們就把重心放在怎樣擺放一個皇后棋子上，擺放基本步驟是：從第1到第8個位置，次序地嘗試將棋子放置在每一個未被控制位置，設(shè)置該棋子所控制格子，將問題變成更小規(guī)模問題向下遞歸，需要注意是每次嘗試一個新未被控制位置前，要將上一次嘗試位置所控制格子復(fù)原。#include<stdio.h>#include<math.h>intqueenPlaces[92][8];intcount=0;intboard[8][8];voidputQueen(intithQueen);//遞歸函數(shù)voidmain(){intn,i,j;for(i=0;i<8;i++){for(j=0;i<8;j++)board[i][j]=-1;for(j=0;j<92;j++)queenPlaces[j][i]=0;}putQueen(0);//從第0個棋子開始擺放

scanf(“%d”,&n);for(i=0;i<n;i++){intith;scanf(“%d”,&ith)f