函数II 递归.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,函数,II,递归,变量的作用域,定义在函数内或块内的变量称为,局部变量（,local variable,）。,在函数外部定义的变量称为,全局变量,(global variable),。,1.,递归的定义,什么是递归？说白了就象我们熟悉的那个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说,。,即递归就是一个对象在定义时用到了自身。,这个对象可以是函数、概念、数学结构,因为故事中包含了故事本身，如果用程序实现，,必然是一个对象（函数）,直接或间接地调用了其自身。,void Story(),cout,“,从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：”,;,cin.get,();/,按任意键听下一个故事,Story();/,老和尚讲的故事，实际上就是上面那个故事,void,Story(int,n),if(n MAX),/,递归的终止条件,cout,从前有座山，山里有座庙，庙里有个老和尚，老和尚对小和尚说了一个故事：,;,cin.get,();,Story(n+1);,else,cout,“,都讲”,MAX“,遍了！你烦不烦哪？,n;,return;,递归的特征,自己调用自己。,直接递归,间接递归,一定要有递归终止的条件，这个条件通常称为边界条件或递归出口。（注：,要确保边界条件能够被执行到,）,递归的使用场合,数据的定义形式按递归定义,问题的求解通过子问题来解决,例：求,n,的阶乘,n!,（,n,！,=1*2*n,）,分析：我们可以这样定义,n!,，,n!=n(n-1)!,，因此求,n!,转化为求,(n-1)!,。这就是一个递归的描述。,因此，可以编写如下递归程序：,int,fac(int,n),if(n,=0)return 1;/,边界条件,return,n*fac(n-1);/else,也可,下图展示了,N=3,的执行过程,递归调用示例图,由此可知，递归的执行过程分递推和回归两个阶段,在递推阶段，把较复杂的问题（规模为,n,）的求解推到比原问题简单一些的问题（规模小于,n,）的求解。例如求,n!,转化为求,(n-1)!,依次类推，直至计算到,n=0,时。在递推阶段，必须要有终止递归的情况。,在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。例如知道,0,！,=1,，可以得到,1,！,=1,，,2,！,=2,，,，直到,n,！,任务：楼梯有,n,阶台阶，上楼可以一步上,1,阶，也可以一步上,2,阶，编一程序计算共有多少种不同的走法。,【,例,】,汉诺塔问题。,有,A,、,B,、,C,三根柱子，,A,柱上有,n,个大小不等的盘子，大盘在下，小盘在上。要求将所有盘子由,A,柱搬动到,C,柱上，每次只能搬动一个盘子，搬动过程中可以借助任何一根柱子，但必须满足大盘在下，小盘在上。打印出搬动的步骤。,A,柱,B,柱,C,柱,分析：,1 A,柱只有一个盘子的情况：,A,柱,C,柱；,2 A,柱有两个盘子的情况：小盘,A,柱,B,柱，大盘,A,柱,C,柱，小盘,B,柱,C,柱。,3 A,柱有,n,个盘子的情况：将此问题看成上面,n-1,个盘子和最下面第,n,个盘子的情况。,n-1,个盘子,A,柱,B,柱，第,n,个盘子,A,柱,C,柱，,n-1,个盘子,B,柱,C,柱。问题转化成搬动,n-1,个盘子的问题，同样，将,n-1,个盘子看成上面,n-2,个盘子和下面第,n-1,个盘子的情况，进一步转化为搬动,n-2,个盘子的问题，,，类推下去，一直到最后成为搬动一个盘子的问题。,这是一个典型的递归问题，递归结束于只搬动一个盘子。,函数的递归调用,算法可以描述为：,1 n-1,个盘子,A,柱,B,柱，借助于,C,柱；,2,第,n,个盘子,A,柱,C,柱；,3 n-1,个盘子,B,柱,C,柱，借助于,A,柱；,其中步骤,1,和步骤,3,继续递归下去，直至搬动一个盘子为止。由此，可以定义两个函数，一个是递归函数，命名为,hanoi(int,n,char source,char temp,char target),，实现将,n,个盘子从源柱,source,借助中间柱,temp,搬到目标柱,target,；另一个命名为,move(char,source,char target),，用来输出搬动一个盘子的提示信息。,程序如下：,#include,void,move(char,source,char,target),cout,target,endl,;,void,hanoi(int,n,char,source,char,temp,char,target),if(n,=1),move(source,target,);,else,hanoi(n-1,source,target,temp);,/,将,n-1,个盘子搬到中间柱,move(source,target,);,/,将最后一个盘子搬到目标柱,hanoi(n-1,temp,source,target);,/,将,n-1,个盘子搬到目标柱,void main(),int,n;,cout,输入盘子数：,n;,hanoi(n,A,B,C,);,任务：用辗转相除法求最大公约数,任务：输入一个整数，用递归算法将整数倒序输出。,N,皇后问题,N,皇后问题在,N*N,的棋盘上放置,N,个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置,2,个皇后），编程求解所有的摆放方法。,八皇后的两组解,分析：,由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正,(“,回溯”思想）。在,N,个皇后未放置完成前，摆放第,I,个皇后和第,I+1,个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。,下面是放置第,I,个皇后的的递归算法,(,伪代码,),：,void,put(int,i)/,搜索第,i,行皇后的位置,if(i=n+1),输出方案；,/,递归出口,for,（,int,j=1;j=,n;j,+,）,/,枚举各种可能，纠正,if(,皇后能放在第,i,行第,j,列的位置,),在第,i,行第,j,列放置第,i,个皇后；,/,试探,put,（,i+1,）；,/,化成和原来相同的子问题,抹去第,i,行第,j,列放置的皇后；,/,纠正,一维数组实现,int,mapmaxn+1=0;,Int,usedmaxn+1=0;,void,put(int,i),if(i=n+1)print,（）；,for,（,int,j=1;j=,n;j,+,）,if(,usedj&check(i,j,),mapi,=j,；,/,试探,put,（,i+1,）；,/,化成和原来相同的子问题,void main(),getinfo,();,put(1);,int,check(int,i,int,j),for(int,k=1;k,I;k,+),if(k-i,)=,abs(mapk-j,)return 0;,return 1;,void print(),for(int,i=1;i=,n;i,+),fout,mapi,;,if(i,n),fout,;,fout,endl,;,