VB递归算法讲解

1、3.5 用递归法解决问题什么是递归法从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事，讲什么呢？从前有座山，山里有座庙，很久以前，有一则古老而有趣的故事，流传至今：蕴含了递归思想递归法包括2种情况：v函数自己调用自己v两个函数之间相互调用 如果一个函数在定义时，直接或间接地调用了自己，这种算法在程序设计中统称为递归法。函数是为了实现某种功能而编写的一段相对独立的程序。自定义函数是指我们自己编写的函数。 标准函数 自定义函数Abs( ) 、len( )、mid( )、chr( )、asc( )自定义函数自定义函数: : 在在VB中，自定中，自定义义函数函数形式形式如下：如下： Public|

2、Private Function (参数参数列列表表) As 类类型型 局部常量局部常量、变量变量定定义义 语语句句组组 函函数数名名称称=返返回值回值 End Function 自定自定义义函数函数的的调调用，可以有用，可以有三种三种格式格式： 变量变量=函函数数名名称（参数）称（参数） Call 函函数数名名称（参数）称（参数） 函函数数名名称称 参数参数子过程的定义Public|private function (参数列表) as 类型 局部常量、变量定义 语句组 函数名称=返回值End functionpublic|private sub (参数列表) 局部常量、变量定义 过程语句组E

3、nd sub自定义函数：自定义函数：子过程的定义：子过程的定义：private sub s(n As Integer) As Long If n = 1 Then s =1 Else s =s(n-1)*n End IfEnd subPublic Function s(n As Integer) As Long If n = 1 Then s =1 Else s =s(n-1)*n End IfEnd Function比较两个数的大小比较两个数的大小 Public Function max(n As Integer) As Integer If ab Then max=a Else max=b

4、 End If End Function Private Sub command_Click() 调用递归函数，显示结果 Print max(3,5) End Sub基本思想: 把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定的程度直到可以直接得出它的解，从而得到原来问题的解。 注意：必须要有一个结束递归的条件，不得无限递归。分析步骤： 1.决定问题规模的参数。 2.问题的边界条件及边界值。 3.解决问题的通式。例:计算一个数的阶乘 1!=1 f(1)=1 2!=1*2 f(2)=f(1)*2 3!=1*2*3 f(3)=f(2)*3

5、 4!=1*2*3*4 f(4)=f(3)*4 5!=1*2*3*4*5 f(5)=f(4)*5 . . n!=1*2*3*4*5*.*n f(n)=f(n-1)*n递归函数求5！ Public Function s(n As Integer) As Long If n = 1 Then s =1 Else s =s(n-1)*n End If End Function Private Sub form_Click() 调用递归函数，显示结果 Print s(5)=; s(5) End Sub递归法的实现递归法的实现 有有人人养养了一对了一对兔兔子子，这对，这对兔兔子子以后以后每每月月生生一一

6、对对兔兔子子，新生新生兔兔子子从从第三个第三个月月开始，也是开始，也是每每月月生生一对一对兔兔子子，问，问12个个月月后这后这人人有多少对有多少对新新生生兔兔子子？问题分析问题分析这个问题是公元前13世纪意大利数学家斐波那契的名著算盘书里的问题。图中每个色块表示一对兔子，其中白色色块表示新生兔子。从图中可以发现，每月新生兔子的对数为：1,1,2,3,5从第三个月起，当月新生兔子数为前两月新生兔子数之和。这个数列在数学上被称做“斐波那契数列”。程序实现程序实现这这个个问题如问题如果果不用不用递归递归法解决，法解决，其其参参考代码考代码如下：如下：Private Function Hares(By

7、Val intMonth As Integer) As IntegerDim i As IntegerDim intCurMon As Integer 当当前月新前月新生生兔兔子子对数对数Dim intPreMon1 As Integer 前前一个一个月新月新生生兔兔子子对数对数Dim intPreMon2 As Integer 前前两个两个月新月新生生兔兔子子对数对数 前前两个两个月月分分别别为为1对对intPreMon1 = 1intPreMon2 = 1 从第从第3月起月起,新新生生兔兔子子为为前前两两月月之之和和For i = 3 To intMonthintCurMon = intP

8、reMon2 + intPreMon1intPreMon1 = intPreMon2intPreMon2 = intCurMonNextHares = intCurMonEnd Function用用递归递归法法实现实现。参参考代码考代码如下：如下： Public Function S(N As Integer) As Integer If N = 1 Or N= 2 Then S = 1 Else S = S(N1) + S(N2) End If End Function年龄问题 有5个人做在一起，问第5个人多大了。他说比第四个人大2岁，问第四个人多大了，他说比第三个人大2岁，问第三个人多大了，他说比第二个人大2岁，问第二个人多大了，他说比第一个人大2岁，最后问第一个人，他说他10岁了。请问第5个人多大了？递归法的归纳1： 递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序递归法的归纳2：递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(