硅谷杂志：基于数据结构的程序递归算法设计 |
| 2012-07-25 09:48 作者：guigu 来源：硅谷网 HV： 编辑： 【搜索试试】
|
|
硅谷网7月25日消息 （原文载于《硅谷》杂志）基于数据结构的程序递归算法设计是当前软件设计中比较的常用的一种方法和技术。由于递归程序算法省略程序设计中的很多操作细节，大大简化程序的设计过程，而且递归程序算法的结构看起来非常清晰，并且程序的易读性也很好，最重要的是递归程序算法的正确性可以比较容易得到验证。总之，递归程序算法在程序设计中的地位非常重要。从对递归算法的介绍谈起，然后对递归算法的实现策略进行系统的分析，最后就递归算法的设计方法及其应用进行深刻的阐述。
1递归算法概述
1.1递归算法的定义
所谓的递归算法，可以这样的理解，如果一个算法能够直接或间接的调用其自身，那么这个算法就称为递归算法。其中递归算法的执行过程就是不断地进行自我调用，一直到执行到递归出口处才结束自我调用的过程，递归算法执行到递归出口后，递归算法将按照调用次序的逆序返回，直到返回到最外层的调用语句时整个递归算法的执行过程才结束。
1.2递归算法的优势
基于数据结构的递归算法是程序设计中一种非常重要的程序设计方法，其在在计算机数学科学中的应用最为广泛，可以解决很多计算机数学方面的问题，从而有效节省了人力资源和时间的成本投入，其中基于数据结构的递归算法的优势主要体现在如下几个方面：
1）对于数学公式的计算，很多数学公式的定义本身就是递归定义。比如，阶乘函数的计算公式，其中当n=1时，n!=1，当n>1时，n!=n*（n-1）!。其程序设计的实现，显然需要用到递归算法。
2）对于计算机学科的数据结构而言，很多知识都需要用到递归算法，比如二叉树以及广义表的实现等。这些特殊的数据结构由于本身所具有的递归特性，其相关的操作算法都是基于递归函数来实现的。
3）还有一类数据结构中的问题，其本身不具有明显的数据结构的特征，但是递归算法的应用可以有效实现问题的简化，提高算法的执行效率。比如数据结构中的快速排序问题以及图的深度优先搜索等问题，虽然不用递归算法也可以进行问题的求解，但是引入递归算法后不仅可以简化程序，而且还可以对算法的时间和空间复杂度进行很好的优化处理。
4）由于递归算法简化了程序设计的很多过程，并且程序结构清晰、并且程序的易读性也很好，其正确性容易得到验证，这就给程序开发人员带来了很大的方便。
2递归算法的实现策略
2.1分治策略
如果有这样的一种操作对象，它可以划分成若干个比较小的而且结构相同的部分，则对原对象的操作可依次递归分解到其各组成部分上，如此递归分解直到数据不可再分为止，我们把这样一种递归算法的实现策略称为分治策略。递归关系的定义以及递归边界的划分就可以根据分治策略很容易得到，从而可以据此来构造出具体的递归函数。举个例子，一颗非空的二叉树是由根结点、根节点的左子树以及根结点的右子树三部分组成的，其中每一部分又都是一颗二叉树。欲设计一个使用递归函数来求二叉树结点总数的算法nodecount（T），该递归算法的定义如下：
intnodecount(BiT)
{intn；
if(T==NULL)
n=0；
else
n=nodecount(T->lchild)+nodecount(T->rchild)+1;
returnn；
}
2.2回溯策略
回溯也是一种基于数据结构递归程序算法的一种问题求解策略，通俗的理解，回溯策略就是让计算机从某种可能的情况出发自动向前进行搜索，在搜索的过程中碰到符合条件的数据就将其保存起来或者输出，当在一条路径上搜索完后就会回到原来的岔路口处重新选择一条还未曾走过的路径重复以前的方式从某种可能的情况出发自动向前进行搜索，不断重复这样的操作，直到求的问题的解或者所有的路径都搜索完为止。回溯策略在进行具体编程实现时通常都用采用的递归算法，不断重复的向前进行搜索就对应着函数的递归调用，其中直到求的问题的解或者所有的路径都搜索完为止的条件对应递归的边界。
3基于数据结构的递归算法的设计方法及其应用
3.1基于数据结构的递归算法的设计方法
基于数据结构的递归算法不仅使一种有效的算法设计方法，还是一种有效的问题分析解决方法。其中实现基于数据结构的递归算法设计的基本思想就是：对于一个整体上比较复杂的问题，将其划分成若干个类似的容易解决的简单的子问题，这样的话，就可以通过递归的思想来实现原问题的递归求解。
需要说明的是，采用基于数据结构的递归算法设计的思想来进行求解的问题需要满足如下两个方面的条件：一是问题本身要具有某种类同自身的子问题描述的性质；二是原问题分解后的子问题要有解存在。基于数据结构的递归算法设计的原则是用自身的情况来定义自身，将问题的求解划分为若干步，通过一步步的分析来确定递归的控制条件，从而求得问题的最终解。其中基于数据结构的递归算法设计的一般格式为：
if边界条件1成立then返回边界值1
elseif边界条件2成立then返回边界值2
.
.
.
else调用解决问题的通用公式
endif
一般条件下，基于数据结构的递归算法的递归调用都是要受到条件控制的，而且调用条件在被调用的过程经常会被作相应的修改，当达到最终结束递归调用的边界条件时，要逐级返回，来求出原问题的解，实现整个递归算法的求解。
3.2基于数据结构的递归算法的应用
3.2.1回文串
如果一个字符串从左向右读和从右向左读完全相同（不区分大小写），则这个字符串称为回文串。可以用递归方法检测一个字符串S是否为回文串。
设S=“ShSh+1….St-1St”，h是第一个字符的位置，t是最后一个字符的位置。
1）若S是空串或长度为1，则S为回文串，否则：
2）若Sh≠St，则S不是回文串，否则，递归地检测S的子串“Sh+1….St-1”。
3.2.2迷宫问题
求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。这类方法即为基于回溯策略的回溯法。
1）求迷宫路径算法的基本思想
若当前位置“可通”，则纳入路径，继续前进；若当前位置“不可通”，则后退，换方向继续探索；若四周“均无通路”，则将当前位置从路径中删除出去。
迷宫可用二维数组maze[m][n]来表示，数组中元素为0的表示通道，为1的表示墙。迷宫的入口处为maze[1][1]，出口处为maze[m-2][n-2]，它们的元素值必为0。任意时刻在迷宫中的位置可用元素的行下标和列下标（i，j）来表示。在位置（i，j）上，可往4个方向走，我们假设出发的优先级是往上、往下、往左、往右。每个点都按照这个优先级来决定下一点的方向。
2）算法的实现
求迷宫中一条路径的算法，可以从入口开始，对每个“当前位置”都从上方向试起，若不能通过，则依次试验下方向、左方向、右方向。当选定一个可通的方向，即找到“下一个位置”后，要把当前所在的位置纳入到探索路径中，并将当前所在的位置以及所选的方向记录下来，以便往下走不通时可顺原路一步步地退回来，每退一步以后接着试在该点上尚未试过的方向，从“下一个位置”开始继续探索，如此重复直至到达出口。
|
|
|
|
【对“硅谷杂志：基于数据结构的程序递归算法设计”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
|
|
