2022年递归算法 .pdf

《2022年递归算法 .pdf》由会员分享，可在线阅读，更多相关《2022年递归算法 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目录1. 课程报告内容概述 . . 2 2. 递归算法介绍 . . 2 3. 递归算法的应用 . . 4 4. 心得体会 . 6 5. 参考文献 . 8 6. 课程报告评价 ( 教师 ) . . 8 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 递归算法第 2 页 共 7 页递归算法1. 课程报告内容概述本课程报告内容主要有递归算法的介绍，递归算法的应用以及我在ACM 学习中的心得体会。2. 递归算法介绍递归是解决一类问题的重

2、要方法。递归算法是算法设计中常用的一种方法，它可以解决具有递归属性的问题，并且是行之有效的。递归算法结构清晰，而且容易用数学归纳法来证明算法的正确性等优点，因此它为设计算法、 调试程序带来很大方便。我们先举一个简单的例子来说明。我们知道，在数学中 N!一般定义为 :N=1*2*3* *(N -1)*N 但也可以用下面公式来定义： 若 N=0 N！1；若 N0 N!= N*(N-1) ！ 在 N0 的公式中，又包括了 (N-1)!，这就是 N!的递归定义。一般说，如果一个对象部分的有自己组成，或者是按他自己定义的，则称之为是递归的。递归在数学和计算机学科中经常遇到。利用递归方法可以用有限的语句来

3、定义无限集合， 但在递归定义中至少要有一条是非递归的，即初始定义。否则就会产生逻辑性错误。在计算机科学中，递归概念还经常用于递归调用方面，即函数或过程自己调用自己。用递归调用的算法就是递归算法。递归调用会产生无终止运算的可能性，因此必须在适当的情况下终止递归调用(也叫做边界条件 )。根据递归定义设计的递归算法中，非递归的初始定义就用做程序的终止条件。递归算法就是算法中有直接或间接调用算法本身的算法。递归算法的要点是：(1)递归就是在过程或函数里调用自身。(2)问题具有类同自身的子问题的性质，被定义项在定义中的应用具有更小的尺度。(3)被定义项在最小尺度上有直接解。(4)在使用递增归策略时，必须

4、有一个明确的递归结束条件，称为递归出口。递归算法设计的原则是用自身的简单情况来定义自身，一步比一步更简单，确定递归的控制条件非常重要。设计递归算法的方法是：(1)寻找方法，将问题化为原问题的子问题的求解。(2)设计递归出口，确定递归终止条件。递归算法设计的难点是递归函数的参数设置和返回值(地址)的设定。如这两名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 递归算法第 3 页 共 7 页个问题没解决好则容易出错。尽管递归算法有如此

5、的优点，但递归算法还是有缺点的，如递归算法的时间效率低，因此有的问题虽然可以用递归法求解，但为了算法的时间效率，还是用非递归法求解为好。另外，(在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。3. 递归算法的应用递归算法的应用首先以汉诺塔问题和树的遍历为例进行分析。（一）汉诺塔问题有三根针A、B、c。A 针上有， 1 个盘子，大的在下，小的在上，要求把这，1 个盘子从 A 针移到 c 针，在移动的过程中可以借助B 针，每次只允许移动一个盘子，且在移动过程中在三根针上都保持大盘在下，小盘在上。关于这个递归问题的实例，教材与一般文献中都是直接介绍移动

6、11，个盘子的算法。对学生来说，一个不确定的数n，概念上太抽象，对算法的理解、依据算法编程带来很大难度。在教学过程中，笔者先从一个确定的数字 (n=3)来分析移动过程，模拟程序的执行过程。假设 A 针上有 3 个(编号为I、 )的盘子移到C 针上 ，现来看一下解决问题的步骤：(1)将 A 针上 2 个(编号为 I、)盘子移到 B 针上(借助 c 针)：1)将 A 针上 I 号盘子移到 c 针上2)将 A 针上号盘子移到B 针上3)将 C 针上 I 号盘子移到B 针上(2)将 A 针上号盘子移到c 针上。(3)将 B 针上 2 个(编号为 I、)盘子移到c 针上(借助 A 针)：1)将 B 针上

7、 I 号盘子移到A 针上2)将 B 针上 号盘子移到C 针上3)将 A 针上 I 号盘子移到C 针上上述 3 个步骤中，(1)、 (3)两步的解法与原来移动3 个盘子的解法完全相同，只是盘子数目减少为2，并且代表源针、工作针、目标针的针代号不同而已；问题可以用递归方法解决，结束递归的条件就是，l= 1 时，只需要简单地把一个盘子从源针移到目标针上即可。 事实上，上面 3 个步骤包含两种操作： (1)将 2 个盘子从一个针移到另一个针上，依据题意， 每次移动过程都是一个对不同数目的盘子进行相似的动作，这是一个递归的过程，用hanoi 函数实现。 (2)将每次移动的最后1 个盘子从一个针上移到另一

8、针上，用move函数实现。通过上述 3 个盘子的移动过程的分析，学生基本能了解盘子移动过程中算名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 递归算法第 4 页 共 7 页法的具体实现，接着依据上述模式，来分析移动n 个盘子的过程。这时，只要将上述程序过程中的数字作相应的改变即可。将凡个盘子从 A 针移到 C 针可以也分解为上述3 个步骤，同样，从上述3个步骤分析可知，其中也包含两种操作：(1)将多个盘子从一个针移到另一个针上，

9、这是一个递归的过程，用hanoi 函数实现 (见程序 1)。(2)将 1 个盘子从一个针上移到另一针上，用move函数实现 (见程序 2)。程序 1：void han (int n，char one ，char two，char three) /将 n 个盘子从 one借助 two 移到 three针上(注意各参数的含义 ) if(n=1) move (one，three)；/递归出口else han (n 一 1，one，three，two)；move(one，three)；han (n一 1，two，one，three)； 程序 2：void move (char getone ，char

10、 putone) coutgetone”_+putoneendl； 就 n 个盘子的移动过程，算法的设计与程序的编写，都与移动3 个盘子很相似，理解起来就容易多了。（二）树的遍历递归的一个典型的应用就是树的遍历。目录系统也是树形的结构，有时我们也可能会对目录树进行遍历，比如进行文件的搜索。 以下是一个对目录进行递归处理的程序，它先处理最上一层目录的中的内容，取得其中的一个元素，判断它是文件还是目录，如果是文件，则列印出它的绝对目录名，如果是一个目录，则进行递归。这个程序中使递归终止的条件是，处理的元素不是目录。 递归函数的参数值总是在文件和目录之间变化。二叉树是数据结构中最常见的存储形式，树与

11、森林都可以转换为二叉树，而遍历算法则是二叉树最重要的操作。在遍历算法中，递归算法是最普遍的，弄清了递归算法及执行时栈的变化情况，可设计出较好的非递归化算法。下面讨论二叉树中序遍历递归算化栈的变化情况。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 递归算法第 5 页 共 7 页二叉树的中序递归遍历算法如下：若二叉树为空，则返回，否则1) 中序遍历左子树(L) 2) 访问根结点(v) 3) 中序遍历右子树(R) 下面以图一为例分析

12、其执行过程中栈的变化情况。递归调用中，每次入栈的内容，包括参数 (即结点信息 )与返回地址，由于返回地址已在流程中反映出来，故在栈中不再列出：分析可看出，每个元素入栈与出栈两次。在第一次出栈时访问它，输出结果为： 4，3，5，2，1，7，6，8，9。4. 心得体会进入大学以后，生活的环境发生了很大变化，我们由一个见识、交往、活动较为狭窄的天地进入到一个见识较为广博，交往活动较为宽阔的天地； 由上课、作业、考试及活动均由老师统一安排，转化为这一切都需要自己设计和安排。因此部分同学就会因为脱离了一定的束缚，在大学期间放任自流。 导致生活无规律、学习也不重视，因此， 我们应该充分认识到我们来到大学仍

13、然应以学习为主，正确的对待学习与其他活动之间的关系。同时，还要注重“学以致用”这一点。我们无论是学习一个应用软件，如World 或 PowerPoint 等，还是学习一门语言，如 C+语言等，我们都应该要敢于动手实践， 而且要勤于动手实践。 有人曾经这么说过：上机时间的多少与计算机应用的水平成正比。名扬海内外的软件WPS的作者求伯君先生曾在一个星期内写出一万行程序代码；而有的计算机专业学生，学了几年电脑，在键盘上敲过的程序代码总数不过几千行。没有量变，哪来的质变？没有实践的积累，哪来的水平的提高？在实践过程中，我们应不断向自己提问题，带着疑点去学习，即使一是解决不了也没关系， 当你在所学的领域

14、内知识积累到一定程度是，问题就会自然迎刃而解了。只有多实践， 才能巩固消化所有的知识， 才能发现问题并感受到解决名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 递归算法第 6 页 共 7 页问题的快乐。计算机科学的研究范畴包括了计算机理论、硬件、软件、网络及应用等，但按照研究的内容，也可以划分为基础理论、专业基础和应用三个层面。在这些研究领域中，我们有结合自身情况，确定正确的学习目标，做到有的放矢。所以以下几门课程必须学好：（1

15、）离散数学。由于计算机所处理的对象是离散型的，所以离散数学是计算机科学的基础，主要研究数理逻辑、集合论、近世代数和图论等。（2）程序设计语言理论。运用数学和计算机科学的理论研究程序设计语言的基本规律，包括形式语言文法理论、形式语义学（如代数语义、公理语义、指称语义等）和计算机语言学等。（3）程序设计方法学。研究如何从好结构的程序定义出发，通过对构成程序的基本结构的分析， 给出能保证高质量程序的各种程序设计规范化方法，并研究程序正确性证明理论、形式化规格技术、形式化验证技术等。（4）计算机组成原理。研究通用计算机的硬件组成以及运算器、控制器、存储器、输入和输出设备等各部件的构成和工作原理。（5）

16、计算机体系结构。研究计算机软硬件的总体结构、计算机的各种新型体系结构（如并行处理机系统、精简指令系统计算机、共享储存结构计算机、阵列计算机、集群计算机、网路计算机、容错计算机等）以及进一步提高计算机性能的各种新技术。计算机科学是以计算机为研究对象的一门学科，它是一门研究范畴十分广泛、发展十分迅速的新兴学科， 在其相关领域的研究中有的方面前人已经研究得比较透彻，需要在后续课程中去学习、掌握和继承， 但在想要攀登到科学顶峰之前，应通晓科学的初步知识， 如未掌握前面的东西， 就永远不要着手做后面的东西，永远不要企图掩饰自己知识上的缺陷，哪怕是用最大的胆推测和假设作为借口来掩饰。不论这种肥皂泡的色彩多

17、么使我们炫目，但肥皂泡必然是要破裂的，于是我们将除了渐愧以外是会无所得的，因此在学习过程中我们不能好高骛远，要养成严格的循序渐进的习惯。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 递归算法第 7 页 共 7 页5. 参考文献1吴文虎 ACM 程序设计习题与解析2 http:/ 09.06.13 3 http:/ 09.06.13 4李永新 汉诺塔问题的非递归算法实现5孟 林 尹德辉 二叉树遍历递归算法非递归讨论6朱 彤递归半递归零递归6. 课程报告评价 (教师 ) 1掌握具体专题， 并能将其应用于实际问题的解决。是（） 否（ ）基本符合（）2课程报告格式符合规范，所附图表清晰。是（） 否（ ）基本符合（）3能按时独立完成课程报告。是（） 否（ ）基本符合（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -