浅议一类递归程序算法的分治和回溯策略

《浅议一类递归程序算法的分治和回溯策略》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅议一类递归程序算法的分治和回溯策略李杰黑龙江省政法管理干部学院150080摘要：递归算法是一种直接或者间接地调用自身的算法。在计算机程序编写中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。文中一方面结合汉诺塔问题和N皇后问题等经典实例介绍了递归程序设计的一般步骤和方法，还介绍了如何通过分治和回溯等策略进行递归程序设计。关键词：递归数据结构算法实现一、引言递归在程序设计基础、数据结构以及算法设计与分析等课程的教学中都占用重要地位，是一类重要的程序设计方法。但递归教学一直是个难点，学生通常会对为何用递归、如何用递

2、归以及递归程序的执行过程存在疑惑。木文旨在解决这一问题，全文以递归为中心，从什么是递归、为何用递归、如何用递归以及使用递归需要注意的问题四个方面组织全文，从方法论的角度对递归程序设计进行了系统的阐述。二、递归程序的实现策略进行递归程序设计的关键是借助递归关系的定义和递归边界构造递归函数，但有些问题的描述中递归关系和递归边界并没有显示给出，称此类问题为隐式递归问题。对于显式递归问题，如前所述，直接根据递归关系的定义和递归边界构造出递归函数即可求解；对于隐式递归问题则要通过一定的策略来找出隐藏的递归关系和递归边界，常见策略如降阶、分治和回溯。三

3、、递归算法的特点递归算法是一种直接或者间接地调用自身的算法。在计算机程序编写中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理递归算法解决问题的特点：1.递归就是在过程或函数里调用自身。2.在使用递归策略吋，必须有一个明确的递归结束条件，称为递归出U。3.递归算法解题通常显得很简洁，但递归算法解题的运行效率较低，所以一般不提倡用递归算法设计程序。4.在递归调用的过程当中系统为每一层的返冋点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。四、递归算法的要求递归算法所体现的“重复

4、”一般有三个要求：1.每次调用在规模上都有所缩小(通常是减半)。2.相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)。3.在问题的规模极小吋必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的人小为条件)，无条件递归调用将会成为死循环而不能正常结束。五、递归算法典型问题一一汉诺塔问题代码如下：#include<stdio.h>voidmove(intn'chara,charb'charc){if(n==l)printf(nt%c->%c"

5、,a,c);//当n只有1个的吋候直接从a移动到celse{move(n-l,a,c,b);//第n-1个要从a通过c移动到bprintf("t%c->%c",a,c);move(n-l,b,a,c);//n-l个移动过来之后b变开始盘，b通过a移动到c，这边很难理解}}main(){intn;printf("请输入要移动的块数：scanf("%d",&n);movefn/a'/b'/c*);}1.分治。若操作对象可定义成由若干结构相同但规模更小的部分组成，则对原对象的操作可递归分解到其各组成部分上分别进行，如此递归分解

6、直到不可再分时停止，此类求解策略称为分治。根据分治策略很容易得到相应的递归关系定义和递归边界,从而构造出具体的递归函数。如非空的二叉树可看作为由根结点、根节点的左子树以及根结点的右子树三部分组成，每一部分又都是一颗树。如右图所示二叉树T(图略)可看作由根节点A、结点B、C构成的左子树和结点D、E、F构成的右子树组成。欲设计递归函数NodeCount(T)求二叉树T的结点总数，显然T的结点数是T的左子树结点数与T的右子树结点数之和再加1，这实际就是递归关系的定义：intNodeCount(BiTreeT){intn;if(T==NULL)n=

7、0;elsen=NodeCount(T->lchild)+NodeCount(T->rchild)+l;returnn;}再注意到空树的结点数为0,依此作递归边界，即可得到表4(略)所示的树结点计数的递归函数。2.冋溯。冋溯也是一种问题求解策略，通常指让计算机从某种可能的情况出发自动向前进行搜索，碰到符合的情况就输出或者保存起来，在一条路径上走到“尽头”后就冋到原来的岔路口选择一条以前没冇走过的路重新向前进行探测，直到找到解或者走完所有路径为止。冋溯具体编程实现时通常都用递归：“向前进行搜索”对应递归调用，“尽头”对应递归边界。

8、比如N皇后问题。题0是说，一个N*N的国际象棋棋盘上主放置N个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的冋一行、同一列、同一条斜线上，要求输出所有可能的摆放方案。其实