浅谈递归算法在程序设计中的运用

浅谈递归算法在程序设计中的运用

Mi o o ue Ap l a o s o 2, . 2 0 c c mp t r r pi t n 1 5 No, 0 9 ci V . 6文章编号： 10 .5X(0 960 6—2 0 77 7 2 0 )-0 30

学习园地

微型电脑应用

2 0年第 2卷第 6期 09 5

浅谈递归算法在程序设计中的运用罗海林摘

金纯

要：递归在计算机科学和数学中都是一个重要的问题求解工具，许多复杂问题的求解都可以用递归算法去解决，适当的

使用递归算法可以简化复杂问题。该文通过具体的实例，讨论了递归算法的实现，并对递归算法进行了进一步的探讨。 关键词：递归；向量数组；算法；循环；

中图分类号：T 3 1 P 1

文献标志码：A下面将通过一个具体的实例说明递归算法如何实现，这个例子用其他算法实现比较困难，但是用递归算法设计思路非常清晰，下面是这个问题的描述：

0引言若一个算法直接或问接调用自己本身，则称这个算法是递归算法，归算法的执行过程是不断地自调用，到到达递直

递归出口才结束自调用过程，到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回，回到最外层的返调用语句时递归算法执行过程结束。…递归算法是程序设计中一种重要的方法，在数学和计算机科学巾，使用递归的思想能解决很多运算量较大的问题，节省大量的人力资源和时问，由于递归算法省略了程序设计中的许多细节操作，简化了程序设计过程，使得在求解许多复杂问题时，采用递归算法比不用递归算法要简单得多，并且程序结构清晰、易读， 正确性容易得到验证，这给用户编制程序和调试程序带来很大的方便。【 】

B国研制出了新式武器——连环阵。但 A国经侦察发现，连环阵其实是由 M个独立武器组成的。这 M个武器编号为 l,…,M。每件武器有两种状态：无敌自卫状态，2

和攻击状态。最初，1号武器处于攻击状态，其他武器都处在无敌自卫状态。以后，一旦第 i 1< (<iM)号武器被消灭， 1秒钟以后第 i1号武器就自动从无敌自卫状态变成攻击状+态。当第 M号武器被消灭以后，连环阵就被彻底摧毁了。 A国经过探测掌握了连环阵中 M个武器的平面坐标， 然后选择了n个点并安放了定时炸弹。 1个

炸弹编号为 1这 1, 2 . 1,,1。每个炸弹的作用半径均为 k,且会持续爆炸 5分钟。在这 5分钟内，每枚炸弹都可以在瞬问消灭离它直线距离不超过 k的、处在攻击状态的 B国武器。和连环阵类似，

1递归算法的思想递归是一种应用归纳的方法求解问题的技术。归算法递求解问题的基本思想是对于较为复杂的问题，原问题分解把

最初 a 1号炸弹持续引爆 5分钟时间，然后 a 2号炸弹持续引爆 5分钟时间，接着 a 3号炸弹引爆……以此类推，直到连环阵被摧毁。在每个炸弹爆炸的时候，其它尚未引爆的炸弹都处于地下隐蔽处，不会被己方的炸弹摧毁。 显然，选好 a、a、a十分重要。好的序列可以在仅 1 2 3.使用较少炸弹的情况下就能将连环阵摧毁；的序列可能在坏使用完所有炸弹后仍无法将连环阵摧毁。现在，请你决定一个序列 a、a、a使得在第 a 1 2 3 x号炸弹引爆的时间内连环阵被摧毁。这里的 x应当尽量小。

成若干个相对简单且类同的子问题，这样原问题就可递推得到求解，适宜用递归算法求解的问题的充分必要条件是：其一

,

问题具有某种可借用的类同自身的子问题描述的性质；

其二，某一有限步的子问题 (也称作本原问题 )直接的解有存在。 递归的前提非常简单：编写一个函数，函数具有调用一该自己来求解问题的能力。其关键在于该函数在调用自己时， 就在堆栈里创建一组新的局部变量，以相当于一个新的函所

下面将具体介绍问题的解决方法的步骤： 21炸弹和武器的数据结构的构造 .每一个炸弹或武器都有横坐标，纵坐标和序号。由此抽象一个 P it o类代表一个炸弹或武器， o t n P i类有三个数据成 n员分别代表炸弹或武器的横坐标，坐标和序号，纵因为 P it o n类需要用到赋值运算符，以增加一个赋值运算符的重载函所数。

数被调用。你唯一需要注意的是函数不能溢出堆栈，并且要有终止条件，程序结束时还要有结束处理代码以保证堆栈通过 rtr(放空问。[ e n) u释 2 j

在通常情况下，递归调用都是要受到条件控制的，而且在被调用的过程中，会对调用条件进行修改，并最终达到结束递归调用并逐级返回，求出原

问题的解。由此可知递归方程式和递归终止条件是递归程序设计的关键，也是递归算 这法设计的难点。

/ o类代表武器或炸弹/ mt Pc s P it lso{ a np bi: ul c

it r; n k mamt

//武器或炸弹的编号/器或炸弹的横坐标 /武

2递归算法的实例说明

,/武器或炸弹的纵坐标P mt o eao (o s P it ) o& prtr=c nt on a∥值运算赋

作者简介：罗海林， E体育学院信息技术t,硕{,上海 2 0 3海 048金纯，上海农林职业技术学院图书信息中心，上海 2 0 3 04 8 6 3

浅谈递归算法在程序设计中的运用

Mi o o u e A p c t n V 1 5 N ., 0 9 c c mp tr p l a o s o 2, o 2 0 r i i . 6

学习园地

微型电脑应用

20 0 9年第 2 5卷第 6期

符“的重载=”}

vco< o t tmp ao s/中间变量用于保存 etrP i e Wep n; n>/v ep n W aos

对于初始条件的炸弹和武器序列，通过用 vco容器来 etr存放 P it的对象 ( on类即炸弹和武器 )。v c rP it o s et< o>b mb; o n /弹的序列/炸

vco P i tmp e iB mb;中间变量用于保 etr o t e R ma o s/< n> n/存v e i o s R ma B mb nv co< o t:e a o eB; e tr P i>: tr t ri r n i t v c o< o t: tr t r tr; etr P i>:eao eW n i i

vco< o t ao s etrP i>wep n; n {器甑詹}武首先从输入文件读入数据，并初始化一个 P it on对象， 保存在 v c r。 et中 o

iv ao s mpy){, f Wep n . t( )/ ( e如果武器序列为空时，递归的出口

2 . 2对于某一个炸弹统计出它能销毁武器的数量武器的序列是有规定的，必须严格的按照武器的序列依次计算，看是否能被炸弹销毁，这个地方非常关键。也就是说，当销毁了第一个武器才能销毁第二个，销毁了第二个才

//如果结果炸弹序列为空或结果炸弹序列的元素数量多于已使用的炸弹序列的数量 irsl lo s mP (l f eu Of mb . t ) ( t 3 e y l(eut

B mb .z( v e i mb. e) ) rsl Of o s i ) R ma Bo s i () se> n s z

能销毁第三个，依次比较进行；第一次循环后满足条件后，才去进行第二次循环；不满足第一次循环的话，出整个循退环。

rsl f o s v e i mb;将已使用的炸弹 eut l mb= R ma Bo s/ O3 n/序列赋给结果炸弹序列)

fr o(第一个武器；最后一个武器；下一个武器){

计算特定的一个炸弹与武器之间的距离；i( f距离<炸弹的作用半径){ 能销毁的武器数量加 1}

//如果武器序列不为空并且未用炸弹序列为空，不满足要求，什么也不做，只提供递归出口es ( Wep n. t(&& v o s mpy){ l i ! a o s mp ) efv e y B mb . t()) e

,/如果武器序列不为空，但未用炸弹序列不为空es{ l e

es{ l e一

旦不满足要求退出循环

) )

c, t/保存调用 f Ids n e函数的返回值 mdn i ac t tm B mb= B mb;/存 v o s e p o sv o s/保 B mb tmp ao sv ao s/ e Wep n= Wep n;/保存 v a o s Wep nt R ma o s v e iB mb;/ e mp e …… 此处隐藏：6894字，全部文档内容请下载后查看。喜欢就下载吧 ……