数据结构(C++)递归.ppt

上传人:p** 文档编号:160520 上传时间:2023-03-02 格式:PPT 页数:44 大小:274KB
下载 相关 举报
数据结构(C++)递归.ppt_第1页
第1页 / 共44页
数据结构(C++)递归.ppt_第2页
第2页 / 共44页
数据结构(C++)递归.ppt_第3页
第3页 / 共44页
数据结构(C++)递归.ppt_第4页
第4页 / 共44页
数据结构(C++)递归.ppt_第5页
第5页 / 共44页
数据结构(C++)递归.ppt_第6页
第6页 / 共44页
数据结构(C++)递归.ppt_第7页
第7页 / 共44页
数据结构(C++)递归.ppt_第8页
第8页 / 共44页
数据结构(C++)递归.ppt_第9页
第9页 / 共44页
数据结构(C++)递归.ppt_第10页
第10页 / 共44页
亲,该文档总共44页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数据结构(C++)递归.ppt》由会员分享,可在线阅读,更多相关《数据结构(C++)递归.ppt(44页珍藏版)》请在第壹文秘上搜索。

1、 一、递归一、递归 二、汉诺塔问题二、汉诺塔问题 三、递归与非递归的转化三、递归与非递归的转化难点难点 优点:优点:采用采用编出的程序简洁、清晰,程序结编出的程序简洁、清晰,程序结构符合结构化程序设计,可读性好。构符合结构化程序设计,可读性好。编译程序是如何处理这类带有递归调用功编译程序是如何处理这类带有递归调用功能的程序的?如果使用了无递归功能的程序设计能的程序的?如果使用了无递归功能的程序设计语言,应该如何设计和实现这类程序呢?语言,应该如何设计和实现这类程序呢? 在定义自身的同时又出现了对自身的调用。在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调如果一个函数在其定义

2、体内直接调用自己,则称直接递归函数。用自己,则称直接递归函数。如果一个函数经过一系列的中间如果一个函数经过一系列的中间调用语句,通过其它函数间接调用自己,则称间调用语句,通过其它函数间接调用自己,则称间接递归函数接递归函数。 数学中常常利用递归手段来定义一些概念,数学中常常利用递归手段来定义一些概念,如求阶乘的运算。如求阶乘的运算。n的阶乘定义为:的阶乘定义为: n * ( n 1 ) ! n0 n! = 1 n=0例如例如: : 显然,该递归的出口是显然,该递归的出口是 0! =1。 long fac (int n) long p; if (n=0| n=1) p=1; else p=n*f

3、ac(n-1) ; return p; void main() long x=fac(5); coutx; long fac (int n) long p; if (n=0 | n=1) p=1; else p=n*fac(n-1) ; return p; 递归函数包含:递归函数包含:1、递归调用语句递归调用语句,如,如 fac (n-1);2、基值判断基值判断,如,如n=0 | n=1即为基值,保证了递归可以即为基值,保证了递归可以终止,满足基值条件后的计算终止,满足基值条件后的计算 p=1, 一般称为最终计算;一般称为最终计算;3、调用之后的返回处理调用之后的返回处理。如。如 p= n *

4、 fac (n-1) ,是返回之,是返回之后要进行的操作。后要进行的操作。fac(5)main()n=5p=5*fac(4)第一层第一层facn=4p=4*fac(3)第二层第二层facn=3p=3*fac(2)第三层第三层facn=2p=2*fac(1)第四层第四层facn=1p=1第五层第五层facfac(2)=2fac(1)=1fac(3)=6fac(4)=24fac(5)=120输出输出假设调用该递归函数的假设调用该递归函数的主函数为主函数为第第0层层,则从主函数调,则从主函数调用递归函数为进入用递归函数为进入第第1层层;从第;从第 i层递归调用本身为进入层递归调用本身为进入“下一层下

5、一层”,即,即第第 i+1 层层。反之,退出第。反之,退出第 i 层递归应返层递归应返回至回至“上一层上一层”,即第,即第 i-1 层。层。递归层次递归层次: : 为了保证递归函数正确执行,系统需设立一个为了保证递归函数正确执行,系统需设立一个“递归递归工作栈工作栈”作为整个递归函数运行期间使用的数据存储区。作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个每一层递归所需信息构成一个“工作记录工作记录”,其中包括,其中包括所有的实参、所有的局部变量以及上一层的返回地址。所有的实参、所有的局部变量以及上一层的返回地址。 每进入一层递归,就产生一个新的工作记录每进入一层递归,就产

6、生一个新的工作记录压入压入栈顶。栈顶。每退出一层递归就从栈顶每退出一层递归就从栈顶弹出弹出一个工作记录,则当前执一个工作记录,则当前执行层的工作记录必须是递归工作栈栈顶的工作记录,称行层的工作记录必须是递归工作栈栈顶的工作记录,称这个记录为这个记录为“活动记录活动记录”,并称指示活动记录的栈顶指,并称指示活动记录的栈顶指针为针为“当前环境指针当前环境指针”。abc1号盘2号盘3号盘abc1号盘2号盘3号盘void Hanoi(int n, char x, char y, char z) if(n = = 1) move(x, 1, z); else Hanoi(n-1, x, z, y); m

7、ove(x, n, z); Hanoi(n-1, y, x, z); 0123456789void move (char x, int n, char y) cout移动移动n号盘子号盘子从柱子从柱子x到柱子到柱子y;Hanoi(n, x, y, z) 可以分成三个子问题:可以分成三个子问题:问题问题1.Hanoi(n-1, x, z, y) /将将X柱上的柱上的n-1个圆盘借助个圆盘借助Z柱移到柱移到Y柱上柱上,此时,此时X柱只剩下第柱只剩下第n个圆盘;个圆盘;问题问题2.Move( n, x, z) /将将X柱上的第柱上的第n个移动到个移动到Z柱柱问题问题3.Hanoi(n-1, y, x

8、, z) /将将Y柱上的柱上的n-1个圆盘借助个圆盘借助X柱移到柱移到Z柱上柱上;n=1时可以直接求解时可以直接求解void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); elseelse Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(

9、n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,4,51递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态(返址,盘号,(返址,盘号,x,y,z)塔与圆盘的状态塔与圆盘的状态盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); elseelse Hanoi(n-1, x, z, y); Hanoi(n-1, x

10、, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,4,52递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态(返址,盘号,(返址,盘号,x,y,z)塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1)

11、move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,3,93递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态(返址,盘号,(返址,盘号,x,y,z)塔与圆盘的状态塔与圆盘的状态6,2,a,c,b6,1,a,b,c盘号盘号123void Hanoi(intvoid Hanoi(

12、int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc6,72递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态(返址,盘号

13、,(返址,盘号,x,y,z)塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1)if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z);

14、 0123456789 0,3,a,b,cabc1,2,3,93递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态(返址,盘号,(返址,盘号,x,y,z)塔与圆盘的状态塔与圆盘的状态6,2,a,c,b8,1,c,a,b盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n

15、-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc8,92递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态(返址,盘号,(返址,盘号,x,y,z)塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1)

16、 move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc6,71递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态(返址,盘号,(返址,盘号,x,y,z)塔与圆盘的状态塔与圆盘的状态盘号盘号123void Hanoi(intvoid Hanoi(int n, char x, char y, char z) n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); elseelse Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > .NET

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!