递归函数-C++

递归函数递归概念设计方法步骤执行过程递归与迭代典型案例【引例1】赏麦粒国际象棋发明人西萨·班·达依尔在国王问赏时说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒……”?需要多少粒麦子f(1)=1;f(2)=2;f(3)=4;……f(n)=2*f(n-1);f(1)+f(2)+……f(64)=264-1=18446744073709551615什么特点？【引例2】汉诺塔问题大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。解决方法要实现将64个圆盘从第一根柱子移到第三根柱子，首先要完成将最上面的63个圆盘移到第二根柱子上，然后再将最下面的一个圆盘移到第三根柱子上。这样，如何移动64个圆盘的问题就转换成了如何移动63个圆盘问题，依次类推，解决问题的规模可以逐步降低为解决移动62、61、60……3、2、1个圆盘的问题。以上两个例子都是递归问题一、递归的概念1、定义2、特点3、典型类型1、定义递归方法是指通过函数或过程调用自身，将问题转化为本质相同但规模较小的子问题的方法。如果是直接调用自身，称为直接递归；如果是通过其它函数或过程间接调用自身，则称为间接递归。递归方法是算法和程序设计中的一种重要技术，是许多复杂算法的基础。A(){……A();……}A(){……B();……}B(){……A();……}直接递归间接递归2、特点原始问题可转化为解决方法相同的新问题；新问题的规模比原始问题小；新问题又可转化为解决方法相同的规模更小的新问题，直至终结条件为止。3、典型类型问题定义是递归的如，阶乘的定义：{1)!1.(nn(n=0)(n0)n!=写成函数形式则为：{1)1(*nfn(n=0)(n0)f(n)=这种函数定义形式是用阶乘函数自己本身定义了自身，故是一种递归定义。数据结构是递归的如前面介绍的链表的结点结构定义：structnode{intdata;structnode*next;}其中，指针域next是指向自身类型的指针，故该数据结构是一种递归数据结构。对于递归数据结构，采用递归方法编写算法简单有效。如：intsum(node*head){if(head==NULL);elsereturn(head-data+);}以上函数用递归算法实现了求解以head做表头指针的链表的所有结点数据的和。return0sum(head-next)问题求解过程是递归的如，前面数组一章中介绍的在有序数组中查找某一数据是否存在于数组中的折半查找算法，其求解过程便是一个递归求解的过程。即不断在前一次区间一半的搜索区间范围内重复着与前一次搜索相同的操作。具体实现后面给出。二、设计方法步骤基本思想：将一复杂问题分解成若干简单且相同的子问题，这样较为复杂的原问题就转换为简单的子问题，而简单到一定程度的子问题可以直接求解，则原问题可递推得到解。递归算法所需条件：•存在递归结束条件及结束时的值•能用递归形式表示，且递归向终止条件发展递归模型：递归模型是递归算法的抽象，反映递归问题的递归结构。以阶乘求解为例，其对应的递归模型为：fun(1)=1(1)fun(n)=n*fun(n-1)n1(2)式子（1）给出了递归的终止条件，被称为递归出口；式子（2）给出了fun(n)与fun(n-1)之间的关系，被称为递归体。设计步骤：•描述递归关系•确定递归出口•写出递归函数intf(intn){if(n==1)return(1);else;}return(n*f(n-1))intfac(intn){if(n==1)return(1);elsereturn(fac(n-1)*n);}voidmain(){inty;y=f(4)couty;}?为什么能计算n!考察程序执行过程:（分为递推和回归两个过程）intfac(intn){if(n==1)return(1);elsereturn(fac(n-1)*n);}intfac(intn){if(n==1)return(1);elsereturn(fac(n-1)*n);}intfac(intn){if(n==1)return(1);elsereturn(fac(n-1)*n);}intfac(intn){if(n==1)return(1);elsereturn(fac(n-1)*n);}第一次调用：n为4第二次调用：n为3第三次调用：n为2第四次调用：n为1三、执行过程返回1返回1*2返回1*2*3返回1*2*3*4分解?递归函数反映一种什么样的思维问题小问题n!(n-1)!问题分解小问题更小问题┆最小问题分解分解不能再分解n!(n-1)!(n-2)!1!四、递归与迭代用迭代法求n!s=1;for(i=1;i=n;i++)s=s*i;迭代过程：1!=12!=1!*23!=2!*3……n!=(n-1)!*n1.迭代与递归的区别？迭代：自底向上的计算过程1!=12!=1!*23!=2!*3……n!=(n-1)!*n递归：自顶向下逐步分解问题，最后自底向上计算递推回归2.迭代与递归的关系每一个递归算法总有一个迭代算法对应效率上，迭代效率高，递归低五、典型案例1、斐波那契数列700多年前，意大利有一位著名数学家斐波那契在他的《算盘全集》一书中提出了一道有趣的兔子繁殖问题。如果有一对兔子，从第三个月开始每个月都生下一对小兔，而所生下的每一对小兔在出生后的第三个月也都生下一对小兔。那么，由一对兔子开始，满一年时一共可以繁殖成多少对兔子？分析：第一、二个月都只有一对兔子，到第三个月第一对兔子生一对小兔，则该月共有2对（1+1=2）兔子。第四个月，第一对兔子又生了一对兔子。因此共有3对（1+2=3）兔子。到第五个月，第一对兔子又生了一对小兔而在第三个月出生的小兔也生下了一对小兔。所以，这个月共有5对（2+3=5）兔子。……规律：从三月份开始兔子总对数，恰好等于前面两个月份兔子总对数的和。因为该月的兔子对总数应该等于上个月的兔子对数加上新出生的小兔对数，而新出生的小兔对数恰好为上上个月的兔子对数（因上上个月的每对兔子到该月都会生出一对新兔子）于是得到每个月的兔子对数：1，1，2，3，5，8，13，21，34，55，89，144，233，377……人们为了纪念这位数学家，就把上面这样的一串数称作斐波那契数列，把这个数列中的每一项数称作斐波那契数。斐波那契数列的递归定义：{1)2()1(1nfibnfibn=1n=2n2fib(n)=f(1)=1,f(2)=1f(n)=f(n-1)+f(n-2)问题子问题1子问题2与f(n)f(n-1)f(n-2)intfib(intn){if()return(1);else}子问题解决了，大问题就解决了递归出口递归体n==1||n==2return(fib(n-1)+fib(n-2));2、猴子吃桃子小猴在一天摘了若干桃，当天吃掉一半多一个，第二天接着吃掉剩下的一半多一个，以后每天都吃掉尚存桃子的一半多一个，第7天早上只剩1个，问小猴摘了多少个桃？分析：由题意知，第n天的桃子个数应是第n+1天个数加1以后的2倍，故可归纳出：递归体：递归出口:f(n)=(f(n+1)+1)*2f(7)=1intf(intn){;else;}递归函数定义如下：if(n==7)return1return(f(n+1)+1)*2值向终止条件方向变化3、十进制整数转换成二至九任意进制数voidf(intn,intr){if(n!=0){f(n/r,r);coutn%r;}}递归出口为n=0最先分解出的最后输出若转换成2~16进制呢？voidf(intn,intr){if()return;else{;coutn%r;}}或：f(n/r,r)调用输出f(100,8)4f(12,8)4f(1,8)1f(0,8)①②③④⑤⑥⑦⑧n==04、二分法查找的递归实现在low和high之间查找在low和mid-1之间查找在mid+1和high之间查找结果是a[mid]intBinary_Search(intlow,inthigh){if()return-1;intmid=(low+high)/2;if(key==a[mid])returnmid;elseif(keya[mid]);else;}lowhighreturnBinary_Search(low,mid-1)returnBinary_Search(mid+1,high)5.数组排序的递归实现假设函数sort（a，n）的功能是将数组a中的n个数进行由小到大排序，n为递归函数的控制参数，当n=1时结束排序。故可将数组拆成两部分：a[0]~a[n-2]和a[n-1]排序可分如下两步进行：1.排好最后一个元素的位置a[n-1]2.调用sort（a，n-1）完成前面n-1个元素的排序a[n-1]a[0]··.a[n-2]sort（a，n-1）voidsort(inta[],intn){inti;if();else{for(i=0;in-1;i++)if(a[i]a[i+1]){intt=a[i];a[i]=a[i+1];a[i+1]=t;};}}n==1return确定最大元素位置sort(a,n-1)控制参数的值向终止条件方向变化6汉诺塔问题有A、B和C三根柱子。A上从上到下按照从小到大的顺序摞着n个圆盘。要求借助B从A上将n个圆盘移到C上。移动规定：一次只能移动1个圆盘，小圆盘上不能放大圆盘递归分析：①借助C从A上将n-1个圆盘移到B上②从A上将1个圆盘移到C上③借助A从B上将n-1个圆盘移到C上大问题：hanoi(n,'A','B','C')子问题1子问题2：子问题3：将n个盘从one座借助two座,移到three座:voidhanoi(intn,charone,chartwo,charthree);hanoi(n-1,'A','C','B');move('A','C');hanoi(n-1,'B,'A','C');#includeiostream.hvoidmain(){;intm;cinm;hanoi(m,'A','B','C');}voidhanoi(intn,charone,chartwo,charthree){;if()move(one,three);else{hanoi(n-1,one,three,two);move(one,three);;}}voidmove(charx,chary){coutx--yendl;}voidhanoi(intn,charone,chartwo,charthree)voidmove(charx,chary)n==1hanoi(n-1,two,one,three)7.递归应用-分形图形数学基础:1975数学家曼德布罗特出版分形几何的专著《分形、机遇和维数》。特征：自相似性。应用：广告、工艺品、建筑、设计布局等。实现：递归算法。不做要求，仅供参考•从一个大的等边三角形开始，将其三条边的中点进行连线，分成相等的4个三角形，•除中间外的3个三角形再重复上述过程，直到满足规定的条件的底层。分形图形1----三角形(x2,y2)(x1,y1)(x3,y3)(x,y)(x,y)三角形中心点坐标(x1,y1)、(x2,y2)、(x3,y3)三角形三个顶点的坐标(x01,y01)、(x02,y02)、(x03,y03)分别代表三个小三角形中心点坐标递归函数drawpic(x,y,len,k)普通参数：x,y:三角形中心点坐标len:三角形边长控制参数：k:递归深度内部其它变量：x1、y1，x2、y2，x3、y3，三角形三个顶点坐标x01、y01，x02、y02，x03、y03，三个小三角形