什么是递归精.ppt

《什么是递归精.ppt》由会员分享，可在线阅读，更多相关《什么是递归精.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、什么是递归第1页，本讲稿共19页引例引例1:需要多少粒麦子需要多少粒麦子?舍罕王打算奖赏国际象棋的发明人舍罕王打算奖赏国际象棋的发明人宰相西萨宰相西萨班班达依尔。国王问达依尔。国王问他想要什么，他对国王说：他想要什么，他对国王说：“陛下，请您在这张棋盘的第陛下，请您在这张棋盘的第1个小格里个小格里赏给我一粒麦子，在第赏给我一粒麦子，在第2个小格里给个小格里给2粒，第粒，第3个小格给个小格给4粒，以后每一粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，格的麦粒，都赏给您的仆人吧！都赏给您的仆人吧！”国王觉得这个要求太容易满

2、足了，就命令给他国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。需要多少粒麦子需要多少粒麦子?f(1)=1;f(n)=2*f(n-1);这是一个递归问这是一个递归问题题f(64)=264-1=18446744073709551615 第2页，本讲稿共19页递归与递归函数递归与递归函数 引例引例1:汉诺塔问题汉诺塔问题:汉诺塔（又称河内塔）问题是源于印度汉诺塔（又

3、称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移放大圆盘，在三根柱子之间一次只能移动一个圆盘。动一个圆盘。演示演示:n=1 n=2 n=3 n=8第3页，本讲稿共19页这是一个递归的

4、问题这是一个递归的问题,需要用递归的方法来解需要用递归的方法来解决决实现思想实现思想:把上面把上面n-1个圆盘由个圆盘由A借助借助C移动到移动到B 把第把第n个圆盘移动到个圆盘移动到C 把把n-1个圆盘由个圆盘由B 借助借助A 移动到移动到Cn个圆盘的移动问题转换成为个圆盘的移动问题转换成为n-1个圆盘的移动问题个圆盘的移动问题,又可又可以继续转化成为以继续转化成为n-2,n-3,3,2,1个圆盘的移动问个圆盘的移动问题题,使问题的规模不断缩小使问题的规模不断缩小第4页，本讲稿共19页1什么是递归？什么是递归？用自身的结构来描述自身就称为递归。用自身的结构来描述自身就称为递归。最典型的例子是对

5、阶乘运算：最典型的例子是对阶乘运算：特点：特点：原始问题可转化为解决方法相同的新问题；原始问题可转化为解决方法相同的新问题；新问题的规模比原始问题小；新问题的规模比原始问题小；新新问问题题又又可可转转化化为为解解决决方方法法相相同同的的规规模模更更小小的的新新问问题题，直至直至终结条件终结条件为止。为止。第5页，本讲稿共19页递推递推回归回归fac(2)=2*fac(1)fac(1)=1fac(4)=4*6fac(3)=3*2fac(2)=2*1fac(3)=3*fac(2)fac(4)=4*fac(3)【例【例5.155.15】编编fac(n)=n!的递归函数的递归函数long fac(in

6、t n)if(n=1)return(1);return(n*fac(n-1);递推过程递推过程每调用自身，当前参数压栈，直到达到递归结束条件。每调用自身，当前参数压栈，直到达到递归结束条件。回归过程回归过程不断从栈中弹出当前的参数，直到栈空。不断从栈中弹出当前的参数，直到栈空。思考：思考：若若fac函数中没有语句函数中没有语句 if(n=1)return(1);程序运行结果将如何？程序运行结果将如何？第6页，本讲稿共19页【例【例5.16】用递归函数实现将一个十进制整数转换成二至十六任意进制】用递归函数实现将一个十进制整数转换成二至十六任意进制的字符的字符 void convert(int m

7、,int r)char b17=0123456789ABCDEF;if(m!=0)convert(m/r,r);coutbm%r;任何有意义的递归必须具有：任何有意义的递归必须具有：递归结束条件及结束时的值递归结束条件及结束时的值（出口）（出口）；能用递归形式表示，并且递归向终止条件发展。能用递归形式表示，并且递归向终止条件发展。优缺点：优缺点：递归算法设计简单，程序代码简洁易读，但它消耗的机时和占递归算法设计简单，程序代码简洁易读，但它消耗的机时和占据的内存空间比非递归大。据的内存空间比非递归大。程序执行过程与参数程序执行过程与参数传递过程传递过程?第7页，本讲稿共19页课堂练习课堂练习1：

8、分析程序的运行结果：分析程序的运行结果：Void f(int n,int r)if(n!=0)f=f(n/r,r);coutn%r;Void main()f(100,8);F(100,8)4F(12,8)4F(1,8)1F(0,8)第8页，本讲稿共19页2递归算法一般用于解决哪些问题？递归算法一般用于解决哪些问题？一般用于解决三类问题：一般用于解决三类问题：(1)数据的定义是按递归定义的。数据的定义是按递归定义的。Fibonacci Sequence f(n)=f(n-1)+f(n-2)出口出口：f(1)=1,f(0)=1阶乘：阶乘：n!=n*(n-1)!出口：出口：1!=1猴子吃桃猴子吃桃这

9、一类问题也可用这一类问题也可用静态变量静态变量或或循环循环来实现来实现第9页，本讲稿共19页递归：递归：#include iostream.h#include iomanip.hlong f(int n)if(n=1)return 1;else if(n=2)return 1;elsereturn f(n-1)+f(n-2);void main()int n;cout输入输入n,求数列的第求数列的第n个数个数n;cout数列的第数列的第n个数：个数：f(n)endl;静态变量：静态变量：long f1(int n)long x;static int x1=1,x2=1;if(n=1)retur

10、n x1;else if(n=2)return x2;else x=x1+x2;x1=x2;x2=x;return x;出口出口递归递归调用调用使用静态变量，使用静态变量，取上一次的计算取上一次的计算结果结果void main()int n,i;cout输入输入n,求数列的第求数列的第n个数个数n;cout数列的第数列的第n个数：个数：endl;coutf(n)endl;for(i=1;i=n;i+)cout f1(i)endl;第10页，本讲稿共19页猴子吃桃猴子吃桃 小猴在一天摘了若干桃，当天吃掉一半多小猴在一天摘了若干桃，当天吃掉一半多一个，第二天接着吃掉剩下的一半多一个，一个，第二天接

11、着吃掉剩下的一半多一个，以后每天都吃掉尚存桃子的一半多一个，以后每天都吃掉尚存桃子的一半多一个，第第7天早上只剩天早上只剩1个，问小猴摘了多少个桃个，问小猴摘了多少个桃？第11页，本讲稿共19页int f(int n)if(n=7)return 1;else return(f(n+1)+1)*2;void main()couthigh 辗转相除法求辗转相除法求m,n最大公约数最大公约数 出口出口:r=0 数制转换数制转换(m转换成转换成r进制）进制）出口出口：m=0递归图形打印递归图形打印第13页，本讲稿共19页汉诺塔汉诺塔#include iostream.h#include iomanip

12、.hvoid hanoi(int n,char one,char two,char three)void move(char getone,char putone);if(n=1)move(one,three);elsehanoi(n-1,one,three,two);move(one,three);hanoi(n-1,two,one,three);void move(char getone,char putone)coutgetoneputoneendl;void main()int m;coutInput the number of disk:m;coutthe steps of movi

13、ngmdisks :1)u1=(x1+x2)/2;u2=(x2+x3)/2;v1=(y1+y2)/2;triangle(u1,x2,u2,v1,y2,k-1);triangle(x1,u1,x2,y1,v1,k-1);triangle(x2,u2,x3,y1,v1,k-1);elseline(x1,y1,x3,y1);line(x1,y1,x2,y2);line(x2,y2,x3,y1);void main()int n;cinn;initgraph(600,600);triangle(30,320,570,30,570,n);getch();closegraph();第16页，本讲稿共19页课堂练习课堂练习2：最大公约数最大公约数#include iostream.hint gcd(int m,int n)if(m%n=0)return n;else returngcd(n,m%n);void main()couthig)return-1;else if(keyamid)low=mid+1;return bisearch(a,low,hig,key);第18页，本讲稿共19页(3)数据的结构形式是按递归定义的。（树的数据的结构形式是按递归定义的。（树的遍历，图的搜索）遍历，图的搜索）第19页，本讲稿共19页