递归算法在ＶＢ程序设计中的实现.doc

《递归算法在ＶＢ程序设计中的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、递归算法在ＶＢ程序设计中的实现递归是一种十分有用代写论文的程序设计技术。在VB程序设计中，递归在算法的描述中被经常采用，很多问题可以用递归算法求解。例如，有些问题的定义形式本身就是递归的，如阶乘函数和Fibonacci数列等；有些数据结构，如二叉树、广义表等，由于结构本身固有的递归特性，所以对它们的操作可以递归进行；还有一类，虽然问题本身没有明显的递归结构，但用递归技术求解比其他方法更容易，如最经典的汉诺塔问题和八皇后问题等。另外，由于递归算法省略了程序设计中的许多细节操作，简化了程序设计过程，使得在求

2、解许多复杂问题时，采用递归算法比不用递归算法要简单得多，并且程序结构清晰、易读，正确性容易验证，这给用户编制程序和调试程序带来很大方便。因此，掌握递归程序设计方法很有必要。但由于递归的设计思想比较巧妙，特别是对于规模较大的问题，掌握递归的算法的设计分析和实现过程是比较困难的，而且相关教程对该部分内容介绍的篇幅甚少，因此，有必要对其进行深入探讨，分析其概念及算法结构特点，分析其设计方法和实现过程，以此来帮助学生加深对递归算法思想的进一步理解，学会正确的应用递归解决实际问题。　　　　一、递归算法的概念　　　

3、　计算机要完成人们预先定义的工作，首先应该设计完成这个工作的步骤和方法，即算法。然后再根据算法编写程序。算法是问题的求解过程的精确描述，求解一个问题往往有多种算法可供选择，选择标准首先是算法的正确性、可靠性、可读性等，其次是算法所需存储空间和时间的消耗。算法设计是一件非常复杂的事情，在处理实际问题时，为了更好地将复杂的问题变得简单，在设计算法时常常采用递归的方法。　　所谓递归，就是指用自身的结构来描述自身，以实现层次数据结构的查询和访问。用递归概念来描述的算法就称为递归算法。递归算法常用于递归调用方面，

4、即子过程或函数自己调用自己。VB允许一个自定义子过程或函数过程在过程体(又称子程序体)的内部调用自己，这样的子过程或函数就叫递归子过程或递归函数。　　递归调用必须是有限的，有限才有意义。所以在进行算法描述时必须设置相关的控制条件，使其成为有限。这可以通过条件语句(If语句)来实现，即只有在设定的条件成立时递归才继续，否则终止递归。可见，构成递归必须满足以下条件：1)有明确的结束递归的边界条件(又称终止条件)以及结束时的边界值；2)过程的描述中包含其本身，即能用递归形式表示，且递归向终止条件发展。　　　　

5、二、递归算法的设计方法　　　　递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求解问题的基本思想是：对于较为复杂的问题，把原问题分解成若干个相对简单且类同的子问题，这样原问题就可递推得到求解。　　当一个问题存在上述构成递归的条件时，该问题便可以利用递归算法进行处理。具体的4设计方法是：当所求解问题难于直接求解时，首先，把问题分解成若干个难度较小、较容易求解的子问题，子问题与原问题具有类同的结构。如果子问题能够直接求解，则解之；如果子问题仍不能直接求解，将每个子问题再分解成若干个

6、更简单的子问题，直到分解出的子问题能够很容易地求解或解为已知，这是实现递归的模板。然后，设计递归出口(即结束递归的边界条件)，在满足出口条件时，递归函数不能再调用自己，必须返回一个确定的值。将这两个方面的问题分析好之后，就可以在子程序体中定义递归调用了。　　在通常情况下，递归调用都是要受到条件控制的，而且在被调用的过程中，会对调用条件进行有规律的修改，直到满足边界条件，返回边界值，结束递归；然后按照原来的路径逐层返回，求出原问题的解。由此可知，递归算法设计的关键在于递归描述和递归终止条件。　　　　　　三

7、、递归算法的实现过程　　　　递归算法的执行过程是不断地自调用，直到到达递归出口才结束。然后，递归算法开始按最后调用的过程最先返回的次序逐层返回，返回到最外层的调用语句时递归算法执行过程结束。可见，递归的实现过程包含了“调用”和“返回”两个阶段。　　许多问题都是可以利用递归算法进行求解的。VB中一个最常用例子就是计算阶乘。例如，用递归函数实现计算N!的求解。代码如下：　　PrivateSubFormClick()　　DimNAsInteger,FAsLong　　N=InputBox(“输入一个正整数：”)

8、　　F=Fact(N)’函数调用　　PrintN；“!=”;F　　EndSub　　PrivateFunctionFact(ByValNAsInteger)AsLong　　IfN=0OrN=1Then　　　　Fact=1　　Else　　　　Fact=N*FactFact(N-1)’函数递归调用　　EndIf　　EndFunction　　运行程序，单击窗体执行FormClick()事件过程，键盘输入3赋给变量N，即求3!的值。程序以Fact(N