VB函数递归与调用.ppt

,函数的递归调用,函数的递归调用 递归:一个函数直接或间接地使用自身。1.直接递归调用：函数直接调用本身 2.间接递归调用：函数间接调用本身,情景1：,小时候，我们听过这样的故事：从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的什么故事呢？从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的什么故事呢？从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的什么故事呢？,故事可以一直讲下去，每一个故事内容都相同，但却是故事里的故事。,程序设计中，函数A自己调用自己，称为直接递归调用。,情景2：,镜子A和镜子B相对放在一起，你会发现什么现象呢？,对了，我们会发现镜子A中有镜子B的映象，镜子B中又镜子A的映象，这样层层叠叠，无穷无尽。,A,B,在程序设计中，像这种函数A调用函数B,函数B再反过来调用函数A的算法，称为间接递归调用。,递归算法的特点：递归函数的执行过程比较复杂，往往都存在着连续的递归调用，其执行过程可分为“递推”和“回归”两个阶段，先是一次一次不断的递推过程，直到符合递推”结束条件，然后是一层一层的回归过程。而其中的每一次递归调用，系统都要在栈中分配空间以保存该次调用的返回地址、参数、局部变量，因此在递推阶段，栈空间一直处于增长状态，然后进入回归阶段，栈空间反向依次释放。直到“递推”过程的终止，在递归的执行过程中，递归结束条件非常重要，它控制“递推”过程的终止，在任何一个递归函数中，递归结束条件都是必不可少的，否则将会一直“递推”下去。导致无穷递归。递归算法的缺点：内存消耗巨大，且连续地调用和返回操作占用较多的CPU时间。递归算法的优点：算法描述简洁易懂。,思考如下问题：,例1:有5个人坐在一起,问第5个人多少岁,他说比第4个人大2岁;问第4个人岁数,他说比第3个人大2岁;问第3个人,又说比第2个大2岁;问第2个人，说比第1个人大2岁；最后问第1个人，他说他10岁；请问第5个人多大?,比她大2岁,比她大2岁,比她大2岁,比她大2岁,我10岁,分析：要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄大2。第一个人的年龄已知，根据第一个人的年龄可依次求得第二、三、四、五个人的年龄。这就是一个递归问题。而每一个人的年龄都比其前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)+2（n1）可以看到，当n1时，求第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）个人年龄的函数，而第（n一1）个人的年龄仍然不知道，还要“回推”到第（n一2）个人的龄，直到第1个人的年龄。此时age(1)已知，不必再向前推了。然后开始第二阶段，采用递推方法，从第1个人的已知年龄推算出第2个人的年龄（12岁），从第2个人的年龄推算出3个人的年龄（14岁），一直推算出第5个人的年龄（18岁）为止。也就是说，一个递归的题可以分为“回推”和“递推”两个阶段。要经历许多步才能求出最后的值。显而易见，如果求递归过程不是无限制进行下去，必须具有一个结束递归过程的条件。例如，age（1）10，就是递归结束的条件。,可以用一个函数来描述上述递归过程：age（n）/*求年龄的递归函数*int n；int c；*c用来存放函数的返回值 if（n=1）c=10;else c=age（n一1）十2；return（c)；main（）/*主函数*printf（%d，age（5）；,例题二 用递归方法求n!分析：假设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数列 Fibonacci数列:1,1,2,3,5,8,13 迭代法求Fibonacci数列的前20项#include void main()int i,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);,迭代法在已知数列前2项的基础上,从第3项开始,依次向后计算,得出数列的每一项,定义Fibonacci数列的递归数学模型：,递归法求Fibonacci数列,递归的终止条件,递归公式,int Fib(int n)if(n0)printf(“error!”);exit(-1);else if(n=1)return 1;else return Fib(n-1)+Fib(n-2);,递归法求Fibonacci数列,用递归法求Fibonacci数列,Fib(4),return 1,递归法是从第n项开始向前计算,当n等于0或1时结束递归调用,开始返回,n=20时,要进行21891次递归调用,思考:求Fibonacci数列的迭代法和递归法谁好？,递归法求Fibonacci数列,16,解析C程序设计第5章 模块化程序设计,2023/7/8,5.2 Hanoi（汉诺）塔问题,例5-4 编程求解Hanoi（汉诺）塔问题。古代有一个梵塔，塔内有三个柱子A、B、C，僧侣们想把A拄子上的一摞盘子移动到C柱子上。最初A拄子上有大小不等的64个盘子，且小的在上，大的在下。在移动过程中，大盘子只能在下，小盘子只能在上，并且每次只能移动一个盘子，可以借助于B柱子。,讨论：汉诺塔问题属于非数值问题，难以用数学公式表达其算法，可以从分析问题本身的规律入手。第一步，问题化简，设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两步具有与原问题相同的性质，只是在问题的规模上比原问题有所缩小，可用递归实现。整理上述分析结果，把第一步作为递归结束条件，将第二步分析得到的算法作为递归算法，可以写出如下完整的递归算法描述：定义一个函数movedisk(int n,char fromneedle,char tempneedle,char toneedle)，该函数的功能是将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,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为例,第一步：A C,以N=3为例,第二步：A B,以N=3为例,第三步：CB,以N=3为例,第四步：AC,以N=3为例,第五步：BA,以N=3为例,第六步：BC,以N=3为例,第七步：AC,八皇后问题,问题描述：会下国际象棋的人都很清楚：皇后可以在横竖斜线上不限步数地吃掉其他棋子，如何将8个皇后放在棋盘上（有8*8个方格），使他们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个、不同的皇后串）。给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。输入数据：第一行是测试数据的组数n，后面跟着n行输入，每组测试数据占1行，包括一个正整数b（1=b=92）。输出要求：n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。输入样例：2192输出样例：15863724,解题思路：1、因为要求出92中不同的摆放方法中的任意一种，所有我们不妨把92中不同的摆放方法一次性求出来，存放在一个数组里。为求解这道题我们需要一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。完成一种摆放时，就要尝试下一种。若要按照字典序将可行摆放方法记录下来，就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试，对于第一个棋子的位置，将第二个棋子从可行的位置从小到大的顺序尝试；在第一和第二个棋子固定的情况下，将第三个棋子从可行的位置从小到大的顺序尝试；以此类推。2、首先，我们有一个8*8的矩阵仿真棋盘标识当前已经摆好的棋子所控制的区域。用一个92行每行8个元素的二维数组记录可行的摆放方法。用一个递归程序实现尝试摆放的过程。基本思想就是假设我们将第一个棋子摆好，并设置它的控制区域，则这个问题就变成了一个7皇后问题，用与8皇后同样的方法可以获得问题的求解。那我们就把重心放在如何摆放一个皇后棋子上，摆放的基本步骤是：从第1到第8个位置，顺序地尝试将棋子放置在每一个未被控制的位置，设置该棋子所控制的格子，将问题变成更小规模的问题向下递归，需要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所控制的格子复原。,#include#include int queenPlaces928;int count=0;int board88;void putQueen(int ithQueen);/递归函数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;if(ithQueen=8)count+;return;for(i=0;i8;i+)if(boardiithQueen=-1)boardiithQueen=ithQueen;/摆放皇后/将其后所有的摆放方法的ith个皇后都放在i+1的位置上/将i增加后，后面的第ith个皇后摆放方法后覆盖此时的设置 for(k=count;k92;k+)queenPlaceskithQueen=i+1;/设置控制范围 for(k=0;k8;k+)for(r=0;r8;r+)if(boardkr=-1),