c++递归函数
递 归 函 数 递归概念 设计方法步骤 执行过程 递归与迭代 典型案例,【引例1】赏麦粒,国际象棋发明人西萨·班·达依尔在国王问赏时说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒” ? 需要多少粒麦子 f(1)=1; f(2)=2; f(3)=4; f(n)=2*f(n-1);,f(64)=264-1=18446744073709551615,什么特点？,【引例2】汉诺塔问题 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。,解决方法 要实现将64个圆盘从第一根柱子移到第三根柱子，首先要完成将最上面的63个圆盘移到第二根柱子上，然后再将最下面的一个圆盘移到第三根柱子上。这样，如何移动64个圆盘的问题就转换成了如何移动63个圆盘问题，依次类推，解决问题的规模可以逐步降低为解决移动62、61、603、2、1个圆盘的问题。,以上两个例子都是递归问题,一、递归的概念 1、定义 2、特点 3、典型类型,1、定义 递归方法是指通过函数或过程调用自身，将问题转化为本质相同但规模较小的子问题的方法。如果是直接调用自身，称为直接递归；如果是通过其它函数或过程间接调用自身，则称为间接递归。递归方法是算法和程序设计中的一种重要技术，是许多复杂算法的基础。,A( ) A( ); ,直接递归,间接递归,2、特点 原始问题可转化为解决方法相同的新 问题； 新问题的规模比原始问题小； 新问题又可转化为解决方法相同的规模更小的新问题，直至终结条件为止。,3、典型类型,问题定义是递归的 如，阶乘的定义：,写成函数形式则为：,这种函数定义形式是用阶乘函数自己本身定义了自身，故是一种递归定义。,数据结构是递归的 如前面介绍的链表的结点结构定义： struct node int data; struct node *next; 其中，指针域next是指向自身类型的指针，故该数据结构是一种递归数据结构。,对于递归数据结构，采用递归方法编写算法简单有效。如： int sum(node *head) if(head=NULL) ; else return(head-data+ ); 以上函数用递归算法实现了求解以head做表头指针的链表的所有结点数据的和。,return 0,sum(head-next),问题求解过程是递归的 如，前面数组一章中介绍的在有序数组中查找某一数据是否存在于数组中的折半查找算法，其求解过程便是一个递归求解的过程。即不断在前一次区间一半的搜索区间范围内重复着与前一次搜索相同的操作。具体实现后面给出。,二、设计方法步骤 基本思想： 将一复杂问题分解成若干简单且相同的子问题，这样较为复杂的原问题就转换为简单的子问题，而简单到一定程度的子问题可以直接求解，则原问题可递推得到解。 递归算法所需条件： 存在递归结束条件及结束时的值 能用递归形式表示，且递归向终止条件发展,递归模型：,递归模型是递归算法的抽象，反映递归问题的递归结构。以阶乘求解为例，其对应的递归模型为： fun(0)=1 (1) fun(n)=n*fun(n-1) n0 (2) 式子（1）给出了递归的终止条件，被称为递归出口；式子（2）给出了fun(n)与fun(n-1)之间的关系，被称为递归体。,设计步骤：,描述递归关系 确定递归出口 写出递归函数,int f(int n) if (n=0) return(1); else ; ,return(n*f(n-1),int fac(int n) if(n=1) return(1); else return(fac(n-1)*n); ,void main() int y; y=f(4) couty; ,? 为什么能计算n! 考察程序执行过程:（分为递推和回归两个过程）,三、执行过程,返回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!=1 2!=1!*2 3!=2!*3 n!=(n-1)!*n,1.迭代与递归的区别？ 迭代：自下向顶的计算过程 1!=1 2!=1!*2 3!=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 人们为了纪念这位数学家，就把上面这样的一串数称作斐波那契数列，把这个数列中的每一项数称作斐波那契数。 斐波那契数列的递归定义：,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);,2、猴子吃桃子 小猴在一天摘了若干桃，当天吃掉一半多一个，第二天接着吃掉剩下的一半多一个，以后每天都吃掉尚存桃子的一半多一个，第7天早上只剩1个，问小猴摘了多少个桃？ 分析： 由题意知，第n天的桃子个数应是第n+1天个数加1以后的2倍，故可归纳出： 递归体：f(n)=(f(n+1)+1)*2 递归出口:f(7)=1,int f(int n) ; else ; ,递归函数定义如下：,if (n=7),return 1,return (f(n+1)+1)*2,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; ,或：,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 (keyamid) ; else ; ,lowhigh,return Binary_Search(low, mid-1),return Binary_Search(mid+1, high),5 汉诺塔问题 有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座: 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');,#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) cout“yendl; ,6、分形图形*,从一个大的等边三角形开始，将其三条边的中点进行连线，分成相等的4个三角形， 除中间外的3个三角形再重复上述过程，直到满足规定的条件的底层。,不做要求，仅供参考,(x,y)三角形中心点坐标 (x1,y1)、 (x2,y2)、 (x3,y3)三角形三个顶点 的坐标,(x01,y01)、 (x02,y02)、 (x03,y03)分别代表三个小三角形中心点坐标,#include “graphics.h“ #include “conio.h“ #include “iostream.h“ #include “math.h“ #define PI 3.14 void drawpic(double x,double y,double len,int k); void main() int n; cinn; /递归深度 initgraph(600,600); /初始化屏幕大小600*600 drawpic(300,300,500,n); getch(); closegraph(); ,三角形中心点坐标,边长,递归深度,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(
