38递归算法实例及程序实现

《38递归算法实例及程序实现》由会员分享，可在线阅读，更多相关《38递归算法实例及程序实现（17页珍藏版）》请在装配图网上搜索。

1、38 递归算法实例及程序实现递归算法实例及程序实现1递归算法的概念递归算法的概念一个过程或函数在其定义或说明中有直接或间接调用自一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，称为递归算法。递归算法的基本思想是把规身的一种方法，称为递归算法。递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同模较大的、较难解决的问题变成规模较小的、容易解决的同一问题，规模较小的问题又变成规模更小的问题，当问题小一问题，规模较小的问题又变成规模更小的问题，当问题小到一定程度时，可以直接得出它的解，从而得到原来问题的到一定程度时，可以直接得出它的解，从而得到原来问题的解。即采

2、用解。即采用“大事化小、小事化了大事化小、小事化了”的基本思想。的基本思想。诸如著名的汉诺塔问题、八皇后问题、斐波那契诸如著名的汉诺塔问题、八皇后问题、斐波那契(Fibonacci)的兔子问题、猴子吃桃问题、年龄问题等都是递的兔子问题、猴子吃桃问题、年龄问题等都是递归问题。归问题。VB允许一个自定义函数在函数体的内部调用自己，这允许一个自定义函数在函数体的内部调用自己，这样的函数就叫递归函数。样的函数就叫递归函数。2递归算法的实现要点递归算法的实现要点递归调用必须是有限制的，有限才有意义。所以在进递归调用必须是有限制的，有限才有意义。所以在进行算法描述时必须设置相关的控制条件，使其成为有限。行

3、算法描述时必须设置相关的控制条件，使其成为有限。这可以通过条件语句这可以通过条件语句(If语句语句)来实现，即只有在设定的条件来实现，即只有在设定的条件成立时递归才继续，否则终止递归。可见，构成递归的必成立时递归才继续，否则终止递归。可见，构成递归的必须满足以下条件：须满足以下条件：(1)有明确的结束递归的边界条件有明确的结束递归的边界条件(又称终止条件又称终止条件)以及以及结束时的边界值；结束时的边界值；(2)函数的描述中包含其本身，即能用递归形式表示，函数的描述中包含其本身，即能用递归形式表示，且递归终止条件的发展。且递归终止条件的发展。3递归算法的设计方法递归算法的设计方法当所求解问题难

4、于直接求解时，首先，把问题分解成当所求解问题难于直接求解时，首先，把问题分解成若干个难度较小、较容易求解的子问题，子问题与原问题若干个难度较小、较容易求解的子问题，子问题与原问题具有类同的结构。如果子问题能够直接求解，则解之；如具有类同的结构。如果子问题能够直接求解，则解之；如果子问题仍不能直接求解，将每个子问题再分解成若干个果子问题仍不能直接求解，将每个子问题再分解成若干个更简单的子问题，直到解出的子问题能够很容易地求解或更简单的子问题，直到解出的子问题能够很容易地求解或解为已知，这是实现递归的模板。然后，设计递归出口解为已知，这是实现递归的模板。然后，设计递归出口(即即结束递归的边界条件结

5、束递归的边界条件)，在满足出口条件时，递归函数不能，在满足出口条件时，递归函数不能再调用自己，必须返回一个确定的值。将这两方面的问题再调用自己，必须返回一个确定的值。将这两方面的问题分析好之后，就可以在程序体中定义递归调用了。分析好之后，就可以在程序体中定义递归调用了。在通常情况下，递归调用都是要受到条件控制的，而在通常情况下，递归调用都是要受到条件控制的，而且在被调用的过程中，会对调用条件进行有规律的修改，且在被调用的过程中，会对调用条件进行有规律的修改，直到满足边界条件，返回边界值，结束递归；然后按原来直到满足边界条件，返回边界值，结束递归；然后按原来的路径逐层返回，求出原问题的解。由此可

6、知，递归算法的路径逐层返回，求出原问题的解。由此可知，递归算法的设计关键在于递归描述和递归终止条件。的设计关键在于递归描述和递归终止条件。如下图所示是递归算法调用过程示意图：如下图所示是递归算法调用过程示意图：4递归算法的实现过程递归算法的实现过程递归算法的过程是不断的自调用，直到到达递归出口才结递归算法的过程是不断的自调用，直到到达递归出口才结束。然后，递归算法开始按最后调用的过程最先返回的次序逐束。然后，递归算法开始按最后调用的过程最先返回的次序逐层返回，返回到最外层的调用语句时递归算法执行过程结束。层返回，返回到最外层的调用语句时递归算法执行过程结束。可见，递归的实现过程包含了可见，递归

7、的实现过程包含了“调用调用”和和“返回返回”两个阶段。两个阶段。许多问题都是可以利用递归算法进行求解的。许多问题都是可以利用递归算法进行求解的。VB中一个最中一个最常用的例子就是计算阶乘。例如，用递归函数实现计算机常用的例子就是计算阶乘。例如，用递归函数实现计算机n！的求解。运行界面如下图所示。的求解。运行界面如下图所示。代码如下：代码如下：Private Sub Command1_Click()Dim n As Integer, m As Doublen Val(Text1.Text)m f(n)Text2.Text Str(n) “的阶乘为的阶乘为” Str(m)End Sub Funct

8、ion f(n As Integer) As DoubleIf n 1 Then f 1Else 参数参数n的值大于的值大于1 f n * f(n 1)递归实现调用自身来计算递归实现调用自身来计算f(n1)的值的值End IfEnd Function注：该示例程序在素材文件夹下注：该示例程序在素材文件夹下vb36文件夹中。文件夹中。本节的学习要求掌握递归算法的基本思想，掌握递本节的学习要求掌握递归算法的基本思想，掌握递归程序的实现要点。学会编写简单的递归函数。考查方归程序的实现要点。学会编写简单的递归函数。考查方式为选择题与填空题。式为选择题与填空题。1下列有关递归的说法，错误的是下列有关递归

9、的说法，错误的是 ()A递法算法的代码一般较少递法算法的代码一般较少B递归算法一定要有终止条件递归算法一定要有终止条件C递归算法体现了大事化小的思想递归算法体现了大事化小的思想D递归函数中可以不包含条件控制语句递归函数中可以不包含条件控制语句D D 2文本框对象文本框对象Text1中的中的Text属性发生改变时，会驱动以下事件处属性发生改变时，会驱动以下事件处理过程理过程Private Sub Text1_Change()If Len(Text1.Text) 8 Then Text1.Text Text1.Text Text1.TextEnd Sub该过程体现的算法思想是该过程体现的算法思想是

10、()A排序算法排序算法 B递归算法递归算法C查找算法查找算法 D解析算法解析算法B3下列下列VB程序模块可以计算正整数程序模块可以计算正整数n阶乘的值。阶乘的值。Function f(n As Integer) As DoubleIf n 1 Then f 1Else f n * f(n 1) End IfEnd Function该模块采用的是该模块采用的是()A查找算法查找算法 B解析算法解析算法C递归算法递归算法 D排序算法排序算法C C 4 有五个人坐在一起，问第有五个人坐在一起，问第5个人多少岁？他说比第个人多少岁？他说比第4个人大个人大2岁，问第四个人岁，问第四个人岁数，他说比第岁数

11、，他说比第3个人大个人大2岁，问第三个人岁数，他说比第二个人大岁，问第三个人岁数，他说比第二个人大2岁，问岁，问第二个人岁数，他说比第第二个人岁数，他说比第1个人大个人大2岁，问第岁，问第1个人岁数，他说他个人岁数，他说他10岁，请问岁，请问第五个人多大？第五个人多大？以下是以下是VB程序代码：程序代码：Public Function age(n As Integer) As LongIf n 1 Then age 10Else age age(n 1) 2End IfEnd FunctionPrivate Sub Command1_Click()MsgBox “第五个人的年龄为第五个人的年龄

12、为” Str(age(5)End Sub该程序采用的算法是该程序采用的算法是_。递归算法递归算法5用递归算法求用递归算法求 1n 个连续自然数的和的个连续自然数的和的VB程序段代码如下：程序段代码如下：Function sum (n A Integer)A Integer求求 1n 个连续自然数的和个连续自然数的和If n 1 Then sum 1Else sum _End IfEnd FunctionPrivate Sub Command1_Click()Inputbox “请输入请输入n的值的值”Msgbox “1n的和为的和为”str(sum(n)End Subn+sum(n-1)划线处

13、应填入的语句是划线处应填入的语句是_。6编写一个编写一个VB程序，实现字符串反序显示。该程序如下图所示：程序，实现字符串反序显示。该程序如下图所示：Function reverse(st As String) As String字符串反序字符串反序If Len(st) 1 Then reverse stElse reverse Right(st, 1) & reverse(Left(st, Len(st) 1)End IfEnd Function Private Sub Command1_Click()Text2.Text _End Sub在文本框Text1中输入一个字符串，点击“返序”按钮C

14、ommand1，在文本框Text2中以反向方式显示该字符串。实现该程序的代码如下：(1)实现该程序的算法是实现该程序的算法是_。(2)划线处应填入的语句是划线处应填入的语句是_。注：该示例程序在素材文件夹下注：该示例程序在素材文件夹下vb37文件夹中。文件夹中。递归算法递归算法reverse(Text1.text) 7编写一个实现将一个十进制整数转换成二进制的编写一个实现将一个十进制整数转换成二进制的VB程序。运行该程序，如下程序。运行该程序，如下图所示。在文本框图所示。在文本框Text1中输入数中输入数n，点击，点击“转换转换”按钮，在标签按钮，在标签Label2中显中显示转换结果。示转换结

15、果。 Private Sub Command1_Click() Dim n As Integer Dim s As String n Val(Text1.Text) s trans(n) Label2.Caption “该数的二进制为：该数的二进制为：” sEnd SubFunction trans(n As Integer) As String If n 1 Then trans n Else trans _ End IfEnd Function(1)实现该程序的算法是实现该程序的算法是_。(2)划线处应填入的语句是划线处应填入的语句是_。递归算法递归算法trans(n2) & (n Mod

16、 2)8回文数是一个数顺着读倒着读都是一样大小的数。例如数：回文数是一个数顺着读倒着读都是一样大小的数。例如数：12321，顺着序倒着读都是同一个数。请在，顺着序倒着读都是同一个数。请在VB中，实现用递归中，实现用递归算法判断一个数是否是回文数。程序运行界面如下所示，在文算法判断一个数是否是回文数。程序运行界面如下所示，在文本框本框Text1中输入一个数，点击中输入一个数，点击“判断判断”按钮按钮Command1，在，在标签标签Label2中显示判断结果。中显示判断结果。程序代码如下：程序代码如下：Function hws(st As String) As Boolean 判断一个数是否是回文

17、数判断一个数是否是回文数 If Len(st) 1 Then hws True Exit Function ElseIf Left(st, 1) Right(st, 1) Then Exit Function End If hws hws(Mid(st, 2, Len(st) 2)End FunctionPrivate Sub Command1_Click() Dim st As String st Text1.Text If _ Then Label2.Caption “该数是回文数该数是回文数” Else Label2.Caption “该数不是回文数该数不是回文数”End IfEnd Sub(1)实现该程序的算法是实现该程序的算法是_。(2)划线处应填入的语句是划线处应填入的语句是_。递归算法递归算法hws(st) 或或hws(st)=True