递归及其在二叉树中的应用
14页1、一、递归的定义一、递归的定义递归:递归: 程序程序调用自身调用自身的编程技巧称为递归。的编程技巧称为递归。 递归函数:是直接调用自己或间接调用自己的函数。递归函数:是直接调用自己或间接调用自己的函数。举例:直观的递归举例:直观的递归 某些数学函数是递归定义的。某些数学函数是递归定义的。求求n n!。!。 具体实现如下:具体实现如下: long long fact(intfact(int n) n) if(nif(n=0) return 1;=0) return 1; else return n*fact(n-1);else return n*fact(n-1); 递归及其在二叉树中的应用递归及其在二叉树中的应用1二阶费波纳奇数列二阶费波纳奇数列具体实现如下:具体实现如下: long long Fib(intFib(int n) n) if(nif(n=0) return 0;=0) return 0; if(nif(n=1) return 1;=1) return 1; return Fib(n-1)+Fib(n-2);return Fib(n-1)+Fib(n-2); 2二、递归函数
2、适用的场合二、递归函数适用的场合在解决现实问题中,对于求解一个复杂的或者问题规在解决现实问题中,对于求解一个复杂的或者问题规 模较大的问题,可以将其模较大的问题,可以将其划分为一些简单的或者规模较划分为一些简单的或者规模较 小的问题小的问题进行解决,如果这种划分满足:进行解决,如果这种划分满足:l l 所划分成的子问题性质与原来的大问题相同。所划分成的子问题性质与原来的大问题相同。 l l 当问题规模小到一定程度的时候直接有解。当问题规模小到一定程度的时候直接有解。对于满足以上条件的问题我们就可以考虑使用递归的对于满足以上条件的问题我们就可以考虑使用递归的 方法求解。方法求解。递归策略只需递归策略只需少量的程序少量的程序就可描述出解题过程所需要的就可描述出解题过程所需要的 多次重复计算多次重复计算,大大地减少了程序的代码量。递归的能,大大地减少了程序的代码量。递归的能 力在于力在于用有限的用有限的语句语句来定义对象的来定义对象的无限集合无限集合。 3hanoihanoi塔问题塔问题问题描述:问题描述: 假设有三个分别命名为假设有三个分别命名为X X、Y Y、Z Z的塔座,在的塔座,在X
3、 X塔座上叠放着塔座上叠放着 n n个小盘压大盘的圆盘堆,要求将塔座个小盘压大盘的圆盘堆,要求将塔座X X上的上的n n个圆盘移至塔个圆盘移至塔 座座Z Z上,并按同样顺序叠放。上,并按同样顺序叠放。要求:要求: 1 1、每次只能移动一个圆盘;、每次只能移动一个圆盘; 2 2、圆盘可以放在、圆盘可以放在X X、Y Y、Z Z中的任意塔座上;中的任意塔座上; 3 3、任何时刻都不能将大盘压在小盘上;、任何时刻都不能将大盘压在小盘上;XYZXYZ4l l 如果有一个盘子,直接从如果有一个盘子,直接从X X移到移到Z Z即可。即可。 l l 如果有如果有n n个盘子要从个盘子要从X X移到移到Z Z,Y Y作为辅助。问题可以转化为,先作为辅助。问题可以转化为,先 将上面将上面n-1n-1个从个从X X移动到移动到Y Y,Z Z作为辅助,然后将第作为辅助,然后将第n n个从个从X X移动到移动到Z Z ,最后将剩余的,最后将剩余的n-1n-1个从个从Y Y移动到移动到Z Z,X X作为辅助。作为辅助。hanoihanoi塔问题塔问题5Void Void hanoihanoi ( ( intin
4、t n, char x, char y, char z ) n, char x, char y, char z ) / /将塔座将塔座X X上按直径由小到大且自上而下编号为上按直径由小到大且自上而下编号为1 1至至n n的的n n个圆盘按规则搬到塔座个圆盘按规则搬到塔座Z Z上,上,Y Y作为辅助塔座。作为辅助塔座。/搬动操作搬动操作move ( x, n, z )move ( x, n, z )if ( n= =1) if ( n= =1)move ( x, 1, z );/ move ( x, 1, z );/将编号为将编号为1 1的圆盘从的圆盘从X X搬到搬到Z Zelse else hanoihanoi ( n-1, x, z, y );/ ( n-1, x, z, y );/将将X X上编号为上编号为1 1至至n-1n-1的的圆盘移到圆盘移到Y Y,Z Z作辅助塔座作辅助塔座move ( x, n, z );/ move ( x, n, z );/将编号为将编号为n n的圆盘从的圆盘从X X搬到搬到Z Zhanoihanoi ( n-1, y, x, z );/ ( n-1,
《递归及其在二叉树中的应用》由会员wt****50分享,可在线阅读,更多相关《递归及其在二叉树中的应用》请在金锄头文库上搜索。
高电压技术 第一章第四节 起始电压与气压的关系
风湿免疫病的新认识与新进展
频数分布表与频数分布直方图1
青岛版九上1.1《平行四边形及其性质》(1)
集团整体业务群的战略安排
金钱_共同面对的话题71171
重要有机物的制备
重性精神疾病的防治培训
酵母醇脱氢酶的提取及专一性测定
高二选修(溶液的酸碱性)2010hy
高二生物必修3《生态系统的物质循环》课件
高一数学集合的基本关系
陈-从梯子的倾斜程度谈起(2)
阿卡宁衍生物合成产物中乙酰胆碱酯酶抑制剂的筛选 -
课题1 海带中碘元素的分离及检验
说不尽的桥课件1
语法--英语词性分类及用法
记忆与知识的储存
解读“引起近视的其它原因”
计算机算法设计与分析(第3版)第2章
2024-02-02 19页
2023-04-10 17页
2023-04-10 17页
2023-04-10 17页
2023-04-06 20页
2022-08-15 67页
2022-08-10 22页
2022-08-10 15页
2022-08-10 40页
2022-07-31 42页