C++递归函数ppt课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,递 归 函 数,递归概念,设计方法步骤,执行过程,递归与迭代,典型案例,1,【,引例,1】,赏麦粒,国际象棋发明人西萨,班,达依尔在国王问赏时说：,“,陛下，请您在这张棋盘的第,1,个小格里赏给我一粒麦子，在第,2,个小格里给,2,粒，第,3,个小格给,4,粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有,64,格的麦粒,”,?,需要多少粒麦子,f(1)=1;,f(2)=2;,f(3)=4;,f(n)=2*f(n-1);,f(64)=2,64,-1=18446744073709551615,什么特点？,2,【,引例,2】,汉诺塔问题,大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着,64,片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。,3,解决方法,要实现将,64,个圆盘从第一根柱子移到第三根柱子，首先要完成将最上面的,63,个圆盘移到第二根柱子上，然后再将最下面的一个圆盘移到第三根柱子上。这样，如何移动,64,个圆盘的问题就转换成了如何移动,63,个圆盘问题，依次类推，解决问题的规模可以逐步降低为解决移动,62,、,61,、,60,3,、,2,、,1,个圆盘的问题。,以上两个例子都是递归问题,4,一、递归的概念,1,、定义,2,、特点,3,、典型类型,5,1,、定义,递归方法是指通过函数或过程调用自身，将问题转化为,本质相同,但,规模较小,的子问题的方法。如果是直接调用自身，称为直接递归；如果是通过其它函数或过程间接调用自身，则称为间接递归。递归方法是算法和程序设计中的一种重要技术，是许多复杂算法的基础。,A(),A();,A(),B();,B(),A();,直接递归,间接递归,6,2,、特点,原始问题可转化为解决,方法相同,的新 问题；,新问题的规模,比原始问题小,；,新问题又可转化为解决方法相同的规模更小的新问题，直至,终结条件,为止。,7,3,、典型类型,问题定义是递归的,如，阶乘的定义：,(,n=0),(n0),n!=,写成函数形式则为：,(,n=0),(n0),f(n)=,这种函数定义形式是用阶乘函数自己本身定义了自身，故是一种递归定义。,8,数据结构是递归的,如前面介绍的链表的结点结构定义：,struct node,int data;,struct node*next;,其中，指针域,next,是指向自身类型的指针，故该数据结构是一种递归数据结构。,9,对于递归数据结构，采用递归方法编写算法简单有效。如：,int sum(node*head),if(head=NULL),;,else,return(head-data+);,以上函数用递归算法实现了求解以,head,做表头指针的链表的所有结点数据的和。,return 0,sum(head-next),10,问题求解过程是递归的,如，前面数组一章中介绍的在有序数组中查找某一数据是否存在于数组中的,折半查找,算法，其求解过程便是一个递归求解的过程。即不断在前一次区间一半的搜索区间范围内重复着与前一次搜索相同的操作。具体实现后面给出。,11,二、设计方法步骤,基本思想：,将一复杂问题分解成若干简单且相同的子问题，这样较为复杂的原问题就转换为简单的子问题，而简单到一定程度的子问题可以直接求解，则原问题可递推得到解。,递归算法所需条件：,存在,递归结束条件及结束时的值,能用递归形式表示，且,递归向终止条件发展,12,递归模型：,递归模型是递归算法的抽象，反映递归问题的递归结构。以阶乘求解为例，其对应的递归模型为：,fun(0)=1 (1),fun(n)=n*fun(n-1)n0 (2),式子（,1,）给出了递归的终止条件，被称为,递归出口,；式子（,2,）给出了,fun(n),与,fun(n-1),之间的关系，被称为,递归体,。,13,设计步骤：,描述递归关系,确定递归出口,写出递归函数,int,f(int,n),if,(n=0),return(1);,else,;,return(n*f(n-1),14,int fac(int n),if(n=1),return(1);,else,return(fac(n-1)*n);,void main(),int y;,y=f(4),couty;,?,为什么能计算,n!,考察程序执行过程,:,（分为递推和回归两个过程）,int fac(int n),if(n=1),return(1);,else,return(fac(n-1)*n);,int fac(int n),if(n=1),return(1);,else,return(fac(n-1)*n);,int fac(int n),if(n=1),return(1);,else,return(fac(n-1)*n);,int fac(int n),if(n=1),return(1);,else,return(fac(n-1)*n);,第一次调用：,n,为,4,第二次调用：,n,为,3,第三次调用：,n,为,2,第四次调用：,n,为,1,三、执行过程,返回,1,返回,1*2,返回,1*2*3,返回,1*2*3*4,15,分解,?,递归函数,反映一种什么样的思维,问题,小问题,n!,(n-1)!,问题,分解,小问题,更小问题,最小问题,分解,分解,不能再分解,n!,(n-1)!,(n-2)!,1!,16,四、递归与迭代,用迭代法求,n!,s=1;,for(i=1;i1,fib(n)=,21,f(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2),问题,子问,题,1,子问,题,2,与,f(n),f(n-1),f(n-2),int fib(int n),if(),return(1);else,与的关系：,子问题解决了，大问题就解决了,递归出口,递归体,n=1|n=2,return(fib(n-1)+fib(n-2);,22,2,、猴子吃桃子,小猴在一天摘了若干桃，当天吃掉一半多一个，第二天接着吃掉剩下的一半多一个，以后每天都吃掉尚存桃子的一半多一个，第,7,天早上只剩,1,个，问小猴摘了多少个桃？,分析：,由题意知，第,n,天的桃子个数应是第,n+1,天个数加,1,以后的,2,倍，故可归纳出：,递归体：,f(n)=(f(n+1)+1)*2,递归出口,:f(7)=1,23,int f(int n),;,else,;,递归函数定义如下：,if(n=7),return 1,return(f(n+1)+1)*2,24,3,、十进制整数转换成二至九任意进制数,void f(int n,int r),if(n!=0),f(n/r,r);,coutn%r;,调用 输出,f(100,8)4,f(12,8)4,f(1,8)1,f(0,8),递归出口为,n=0,最先分解出的最后输出,若转换成,216,进制呢？,void f(int n,int r),if(n=0),return;,else,f(n/r,r);,coutn%r;,或：,25,4,、二分法查找的递归实现,在,low,和,high,之间查找,在,low,和,mid-1,之间查找,在,mid+1,和,high,之间查找,结果是,amid,int Binary_Search(int low,int high),if()return-1;,int mid=(low+high)/2;,if(key=amid)return mid;,else if(keyhigh,return Binary_Search(low,mid-1),return Binary_Search(mid+1,high),26,5,汉诺塔问题,有,A,、,B,和,C,三根柱子。,A,上从上到下按照从小到大的顺序摞着,n,个圆盘。要求借助,B,从,A,上将,n,个圆盘移到,C,上。移动规定：一次只能移动,1,个圆盘，小圆盘上不能放大圆盘,递归分析：,借助,C,从,A,上将,n-1,个圆盘移到,B,上,从,A,上将,1,个圆盘移到,C,上,借助,A,从,B,上将,n-1,个圆盘移到,C,上,27,大问题,：,hanoi(n,A,B,C),子问题,1,子问题,2,：,子问题,3,：,将,n,个盘从,one,座借助,two,座,移到,three,座,:,void hanoi(int n,char one,char two,char three);,hanoi(n-1,A,C,B);,move(A,C);,hanoi(n-1,B,A,C);,28,#include iostream.h,void main(),void hanoi(int n,char one,char two,char three);,int m;,cinm;,hanoi(m,A,B,C);,void hanoi(int n,char one,char two,char three),void move(char x,char y);,if(n=1),move(one,three);,else,hanoi(n-1,one,three,two);,move(one,three);,hanoi(n-1,two,one,three);,void move(char x,char y),coutyn;/,递归深度,initgraph(600,600);/,初始化屏幕大小,600*600,drawpic(300,300,500,n);,getch();,closegraph();,三角形中心点坐标,边长,递归深度,32,void drawpic(double x,double y,double len,int k),double x1,y1,x2,y2,x3,y3,x01,y01,x02,y02,x03,y03;,if(k=1),x1=x-len/2;y1=y+len/2*tan(PI/6);,x2=x+len/2;y2=y+len/2*tan(PI/6);,x3=x;y3=y-len*tan(PI/6);,line(x1,y1,x2,y2);,line(x2,y2,x3,y3);,line(x3,y3,x1,y1);,else,x01=x-len/4;y01=y+len*tan(PI/6)/4;,x02=x+len/4;y02=y+len*tan(PI/6)/4;,x03=x;y03=y-len*tan(PI/6)/2;,drawpic(x01,y01,len/2,k-1);,drawpic(x02,y02,len/2,k-1);,drawpic(x03,y03,len/2,k-1);,递归出口,33,