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

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

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

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

4、内部调用自己， 这样的子过程或函数就叫递归子过程或递归函数。 递归调用必须是有限的，有限才有意义。所以在进行算法描述时必须设置相关的控制条 件，使其成为有限。这可以通过条件语句(If语句)来实现，即只有在设定的条件成立时递归 才继续，否则终止递归。可见，构成递归必须满足以下条件：1)有明确的结束递归的边界 条件(又称终止条件)以及结束时的边界值；2)过程的描述中包含其本身，即能用递归形式 表示，且递归向终止条件发展。 二、递归算法的设计方法 递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求 解问题的基本思想是：对于较为复杂的问题，把原问题分解成若干个相对简单且类同的

5、子问 题，这样原问题就可递推得到求解。 当一个问题存在上述构成递归的条件时，该问题便可以利用递归算法进行处理。具体的 设计方法是：当所求解问题难于直接求解时，首先，把问题分解成若干个难度较小、较容易 求解的子问题，子问题与原问题具有类同的结构。如果子问题能够直接求解，则解之；如果 子问题仍不能直接求解，将每个子问题再分解成若干个更简单的子问题，直到分解出的子问 题能够很容易地求解或解为已知，这是实现递归的模板。然后，设计递归出口(即结束递归 的边界条件)，在满足出口条件时，递归函数不能再调用自己，必须返回一个确定的值。将 这两个方面的问题分析好之后，就可以在子程序体中定义递归调用了。 在通常情

6、况下，递归调用都是要受到条件控制的，而且在被调用的过程中，会对调用条 件进行有规律的修改，直到满足边界条件，返回边界值，结束递归；然后按照原来的路径逐 层返回，求出原问题的解。由此可知，递归算法设计的关键在于递归描述和递归终止条件。   三、递归算法的实现过程 递归算法的执行过程是不断地自调用，直到到达递归出口才结束。然后，递归算法开始 按最后调用的过程最先返回的次序逐层返回，返回到最外层的调用语句时递归算法执行过程 结束。可见，递归的实现过程包含了“调用”和“返回”两个阶段。 许多问题都是可以利用递归算法进行求解的。VB中一个最常用例子就是计算阶乘。例如 ，用递归函数实现计算N!的

7、求解。代码 Private Sub FormClick() Dim N As Integer,F As Long N=InputBox(“输入一个正整数：”) F=Fact(N) 函数调用 Print N；“!=”;F End Sub Private Function Fact(ByVal N As Integer)As Long If N=0 Or N=1 Then Fact=1 Else          Fact=N*Fact Fact(N-1) 函数递归调用 End If End Function 运行程序

8、，单击窗体执行Form Click()事件过程，键盘输入3赋给变量N，即求3!的值。 程序以Fact(N)形式调用函数Fact。当函数Fact开始运行时，首先检测传递过来的参数 N值 是否为1，若为1，则函数返回值为1;若不为1，函数执行赋值语句Fact=N*Fact(N-1)。函数 调用传递的参数N是3，函数计算表达式3*Fact(3-1)值，由于表达式中还有函数调用，于是V B第二次调用Fact函数，但传递的参数是2，函数计算表达式2*Fact(2-1)值。当再一次调用 此函数时，参数值为1，因此函数返回值1到本次调用点，此调用函数又返回2的值到调用这 个调用函数的函数；最后，最初被调用的

9、函数返回6到调用它的过程，得到运行结果。递归 函数Fact的调用和返回过程如图1所示。 图1 递归函数Fact的调用从图1可以看出，一个递归问题可以分为“调用”和“返回”两个阶段。当进入调用阶 段后，便逐层向下调用，因此Fact函数被调用3次，即Fact（3)、Fact(2)、Fact(1)，直到 遇到终止条件(即当N=1时Fact=1)。然后带着终止条件所给的函数值进入返回阶段。按照原 来的路径逐层返回，由Fact(1)推出Fact(2)，由Fact(2)推出Fact(3)为止。 一般来讲，从算法描述的角度看，递归算法通常有两种实现方法。一种是在递归函数中用递 归公式实现。上述的计算阶乘就是

10、一个使用递归公式的常用例子，其中Fact=N*Fact（N-1) 就是递归公式。再如，求Fibonacci数列的问题，也是通过递归公式来实现递归调用的。其 递归函数代码段 图2 汉诺塔(hanoi)问题Private Function Fab(ByVal N As Integer)As Long If N=1 Or N=2 Then Fab=1 递归出口 Else Fab=Fab(N-2)+Fab(N-1) 递归公式 End If End Function 有些问题无法直接使用递归公式，而要通过一个递归过程来描述。例如，大家所熟知的 汉诺塔问题：有A、B、C三个塔座，A塔上有直径从小到大的N个

11、盘子(如图2所示)，要求借助 塔B将N个盘子由A移到C，且保证：每次只移动一个盘子，任何时刻不能把大盘子置于小盘子 之上。 此问题可以用一个递归过程描述：(1)借助C，将（N-1）个盘子从A座移动到B座：(2)将 最后一个盘子(最下端的)从A座移动到C座：(3）滞助A，将(N-1)个盘子从B座移动到 C座。 依据以上分析，(1)和(3)步属于同类问题，只是参数值不同而已。由此可写出递归算法 ，并用VB程序描述的递归过程代码段 Private Sub MoveDisk(N As Integer,A As String，B As String,C As String) If N=1 Then Pr

12、int “将第1个圆盘从第”&A&“座移到第”&C&“座” Else Call MoveDisk(N-1，A，C，B) 过程递归调用 Print“将第”&N&“个圆盘从第”&A&“座移到第”n&C&“座” Call MoveDisk(N-1，B，A，C) 过程递归调用 End If End Sub 此程序根据对问题的递归描述写出，结构清楚，易理解。因涉及递归，所以其调用的执行过 程可能很复杂。但如果不用递归方法，问题又可能很难处理。因此，在算法描述过程中，只 需把以上算法的三步过程设计好，再考虑一个盘子时的情况(递

13、归出口)怎样处理就可以了。 从上述分析中，可以认为，看问题能否用递归算法，先不要考虑具体的执行过程，只要满足 上述 构成递归的条件即可。在VB程序设计中使用递归时还应注意，在定义递归函数 或递归过程时，一般先使用If语句进行递归测试，找到递归结束的条件，然后再进行递归调 用。 以上示例是递归应用的典型。很多人认为递归不易理解，这是把递归狭隘化了，但是对 递归的理解不能因此受到限制，递归程序的复杂程度比一般程序要高很多。递归算法使程序 清晰直观，是程序设计中很重要的方面，但递归在计算机中的执行过程却很复杂，需要占用 较大的内存空间和较多的系统时间来进行频繁进出和转移操作，执行效率很低。所以，在VB 程序设计过程中，并不一味追求递归。如果一个问题的求解过程明显是递推规律或通过循 环处理方法即可方便解决的，则不必要使用递归。反之，在对问题进行分解、求解的过程中 得到的是和原问题性质相同的子问题，由此自然得到一个递归算法，且它比实现非递归算法 更符合