《【最新word论文】递归算法在ＶＢ程序设计中的实现【高等教育专业论文】》由会员分享，可在线阅读，更多相关《【最新word论文】递归算法在ＶＢ程序设计中的实现【高等教育专业论文】（4页珍藏版）》请在金锄头文库上搜索。
1、1递归算法在程序设计中的实现递归是一种十分有用代写论文的程序设计技术。在 VB 程序设计中，递归在算法的描述中被经常采用，很多问题可以用递归算法求解。例如，有些问题的定义形式本身就是递归的，如阶乘函数和 Fibonacci 数列等；有些数据结构，如二叉树、广义表等，由于结构本身固有的递归特性，所以对它们的操作可以递归进行；还有一类，虽然问题本身没有明显的递归结构，但用递归技术求解比其他方法更容易，如最经典的汉诺塔问题和八皇后问题等。另外，由于递归算法省略了程序设计中的许多细节操作，简化了程序设计过程，使得在求解许多复杂问题时，采用递归算法比不用递归算法要简单得多，并且程序结构清晰、易读，正确性
2、容易验证，这给用户编制程序和调试程序带来很大方便。因此，掌握递归程序设计方法很有必要。但由于递归的设计思想比较巧妙，特别是对于规模较大的问题，掌握递归的算法的设计分析和实现过程是比较困难的，而且相关教程对该部分内容介绍的篇幅甚少，因此，有必要对其进行深入探讨，分析其概念及算法结构特点，分析其设计方法和实现过程，以此来帮助学生加深对递归算法思想的进一步理解，学会正确的应用递归解决实际问题。一、递归算法的概念计算机要完成人们预先定义的工作，首先应该设计完成这个工作的步骤和方法，即算法。然后再根据算法编写程序。算法是问题的求解过程的精确描述，求解一个问题往往有多种算法可供选择，选择标准首先是算法的正
3、确性、可靠性、可读性等，其次是算法所需存储空间和时间的消耗。算法设计是一件非常复杂的事情，在处理实际问题时，为了更好地将复杂的问题变得简单，在设计算法时常常采用递归的方法。所谓递归，就是指用自身的结构来描述自身，以实现层次数据结构的查询和访问。用递归概念来描述的算法就称为递归算法。递归算法常用于递归调用方面，即子过程或函数自己调用自己。VB 允许一个自定义子过程或函数过程在过程体(又称子程序体)的内部调用自己，这样的子过程或函数就叫递归子过程或递归函数。递归调用必须是有限的，有限才有意义。所以在进行算法描述时必须设置相关的控制条件，使其成为有限。这可以通过条件语句(If 语句)来实现，即只有在
4、设定的条件成立时递归才继续，否则终止递归。可见，构成递归必须满足以下条件：1)有明确的结束递归的边界条件(又称终止条件)以及结束时的边界值；2)过程的描述中包含其本身，即能用递归形式表示，且递归向终止条件发展。二、递归算法的设计方法递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求解问题的基本思想是：对于较为复杂的问题，把原问题分解成若干个相对简单且类同的子问题，这样原问题就可递推得到求解。当一个问题存在上述构成递归的条件时，该问题便可以利用递归算法进行处理。具体的设计方法是：当所求解问题难于直接求解时，首先，把问题分解成若2干个难度较小、较容易求解的子问题，子问题与
5、原问题具有类同的结构。如果子问题能够直接求解，则解之；如果子问题仍不能直接求解，将每个子问题再分解成若干个更简单的子问题，直到分解出的子问题能够很容易地求解或解为已知，这是实现递归的模板。然后，设计递归出口(即结束递归的边界条件)，在满足出口条件时，递归函数不能再调用自己，必须返回一个确定的值。将这两个方面的问题分析好之后，就可以在子程序体中定义递归调用了。在通常情况下，递归调用都是要受到条件控制的，而且在被调用的过程中，会对调用条件进行有规律的修改，直到满足边界条件，返回边界值，结束递归；然后按照原来的路径逐层返回，求出原问题的解。由此可知，递归算法设计的关键在于递归描述和递归终止条件。三、
6、递归算法的实现过程递归算法的执行过程是不断地自调用，直到到达递归出口才结束。然后，递归算法开始按最后调用的过程最先返回的次序逐层返回，返回到最外层的调用语句时递归算法执行过程结束。可见，递归的实现过程包含了“调用”和“返回”两个阶段。许多问题都是可以利用递归算法进行求解的。VB 中一个最常用例子就是计算阶乘。例如，用递归函数实现计算 N!的求解。代码如下：PrivateSubFormClick()DimNAsInteger,FAsLongN=InputBox(“输入一个正整数：”)F=Fact(N)函数调用PrintN；“!=”;FEndSubPrivateFunctionFact(ByVal
7、NAsInteger)AsLongIfN=0OrN=1ThenFact=1ElseFact=N*FactFact(N-1)函数递归调用EndIfEndFunction运行程序，单击窗体执行 FormClick()事件过程，键盘输入 3 赋给变量 N，即求 3!的值。程序以 Fact(N)形式调用函数 Fact。当函数 Fact 开始运行时，首先检测传递过来的参数 N 值是否为 1，若为 1，则函数返回值为 1;若不为 1，函数执行赋值语句 Fact=N*Fact(N-1)。函数调用传递的参数 N 是 3，函数计算表达式 3*Fact(3-1)值，由于表达式中还有函数调用，于是 VB 第二次调用
8、 Fact 函数，但传递的参数是 2，函数计算表达式 2*Fact(2-1)值。当再一次调用此函数时，参数值为 1，因此函数返回值 1 到本次调用点，此调用函数又返回 2 的值到调用3这个调用函数的函数；最后，最初被调用的函数返回 6 到调用它的过程，得到运行结果。递归函数 Fact 的调用和返回过程如图 1 所示。图 1 递归函数 Fact 的调用从图 1 可以看出，一个递归问题可以分为“调用”和“返回”两个阶段。当进入调用阶段后，便逐层向下调用，因此 Fact 函数被调用 3 次，即 Fact（3)、Fact(2)、Fact(1)，直到遇到终止条件(即当 N=1 时Fact=1)。然后带着
9、终止条件所给的函数值进入返回阶段。按照原来的路径逐层返回，由 Fact(1)推出 Fact(2)，由 Fact(2)推出 Fact(3)为止。一般来讲，从算法描述的角度看，递归算法通常有两种实现方法。一种是在递归函数中用递归公式实现。上述的计算阶乘就是一个使用递归公式的常用例子，其中 Fact=N*Fact（N-1)就是递归公式。再如，求 Fibonacci 数列的问题，也是通过递归公式来实现递归调用的。其递归函数代码段如下：图 2 汉诺塔(hanoi)问题 PrivateFunctionFab(ByValNAsInteger)AsLongIfN=1OrN=2ThenFab=1递归出口Else
10、Fab=Fab(N-2)+Fab(N-1)递归公式EndIfEndFunction有些问题无法直接使用递归公式，而要通过一个递归过程来描述。例如，大家所熟知的汉诺塔问题：有 A、B、C 三个塔座，A 塔上有直径从小到大的 N 个盘子(如图 2 所示)，要求借助塔 B 将 N 个盘子由 A 移到 C，且保证：每次只移动一个盘子，任何时刻不能把大盘子置于小盘子之上。此问题可以用一个递归过程描述：(1)借助 C，将（N-1）个盘子从 A 座移动到 B 座：(2)将最后一个盘子(最下端的)从 A 座移动到 C 座：(3）滞助 A，将(N-1)个盘子从 B 座移动到 C 座。依据以上分析，(1)和(3)
11、步属于同类问题，只是参数值不同而已。由此可写出递归算法，并用 VB 程序描述的递归过程代码段如下：PrivateSubMoveDisk(NAsInteger,AAsString，BAsString,CAsString)IfN=1ThenPrint“将第 1 个圆盘从第”&A&“座移到第”&C&“座”ElseCallMoveDisk(N-1，A，C，B)过程递归调用Print“将第”&N&“个圆盘从第”&A&“座移到第”n&C&“座”CallMoveDisk(N-1，B，A，C)过程递归调用EndIfEndSub此程序根据对问题的递归描述写出，结构清楚，易理解。因涉及递归，所以4其调用的执行过程
12、可能很复杂。但如果不用递归方法，问题又可能很难处理。因此，在算法描述过程中，只需把以上算法的三步过程设计好，再考虑一个盘子时的情况(递归出口)怎样处理就可以了。从上述分析中，可以认为，看问题能否用递归算法，先不要考虑具体的执行过程，只要满足上述构成递归的条件即可。在 VB 程序设计中使用递归时还应注意，在定义递归函数或递归过程时，一般先使用 If 语句进行递归测试，找到递归结束的条件，然后再进行递归调用。以上示例是递归应用的典型。很多人认为递归不易理解，这是把递归狭隘化了，但是对递归的理解不能因此受到限制，递归程序的复杂程度比一般程序要高很多。递归算法使程序清晰直观，是程序设计中很重要的方面，
13、但递归在计算机中的执行过程却很复杂，需要占用较大的内存空间和较多的系统时间来进行频繁进出和转移操作，执行效率很低。所以，在 VB 程序设计过程中，并不一味追求递归。如果一个问题的求解过程明显是递推规律或通过循环处理方法即可方便解决的，则不必要使用递归。反之，在对问题进行分解、求解的过程中得到的是和原问题性质相同的子问题，由此自然得到一个递归算法，且它比实现非递归算法更符合人们的思维逻辑，则应该使用递归。因此，使用递归应扬长避短，只有真正掌握递归这个有效的编程方法，才能提高编程能力和编程效率。参考文献：1牛又奇，孙建国VisualBASIC 程序设计教程M 苏州：苏州大学出版社，20072霍红卫算法设计与分析M 西安：西安电子科技大学出版社，20053苗英恺递归程序的教学探讨J 电脑知识与技术，2008(2)4符策锐基于 VB 的递归模拟演示程序的实现J 电脑开发与应用，2008(5)
