VB递归算法讲解

3.5用递归法解决问题什么是递归法从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事，讲什么呢？从前有座山，山里有座庙，……很久以前，有一则古老而有趣的故事，流传至今：蕴含了递归思想递归法包括2种情况：函数自己调用自己两个函数之间相互调用如果一个函数在定义时，直接或间接地调用了自己，这种算法在程序设计中统称为递归法。函数是为了实现某种功能而编写的一段相对独立的程序。自定义函数是指我们自己编写的函数。•标准函数•自定义函数Abs()、len()、mid()、chr()、asc()……自定义函数:•在VB中，自定义函数形式如下：•[Public|Private]Function函数名称([参数列表])[As类型]•局部常量、变量定义•语句组•函数名称=返回值•EndFunction•自定义函数的调用，可以有三种格式：•变量=函数名称（参数）•Call函数名称（参数）•函数名称参数子过程的定义[Public|private]function函数名称([参数列表])[as类型]局部常量、变量定义语句组函数名称=返回值Endfunction[public|private]sub子过程名称([参数列表])局部常量、变量定义过程语句组Endsub自定义函数：子过程的定义：•privatesubs(nAsInteger)AsLong•Ifn=1Then•s=1•Else•s=s(n-1)*n•EndIf•Endsub•PublicFunctions(nAsInteger)AsLong•Ifn=1Then•s=1•Else•s=s(n-1)*n•EndIf•EndFunction比较两个数的大小•PublicFunctionmax(nAsInteger)AsInteger•IfabThen•max=a•Else•max=b•EndIf•EndFunction•PrivateSubcommand_Click()'调用递归函数，显示结果•Printmax(3,5)•EndSub基本思想:•把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定的程度直到可以直接得出它的解，从而得到原来问题的解。•注意：必须要有一个结束递归的条件，不得无限递归。分析步骤：•1.决定问题规模的参数。•2.问题的边界条件及边界值。•3.解决问题的通式。例:计算一个数的阶乘•1!=1f(1)=1•2!=1*2f(2)=f(1)*2•3!=1*2*3f(3)=f(2)*3•4!=1*2*3*4f(4)=f(3)*4•5!=1*2*3*4*5f(5)=f(4)*5•…….……..•n!=1*2*3*4*5*….*nf(n)=f(n-1)*n递归函数求5！•PublicFunctions(nAsInteger)AsLong•Ifn=1Then•s=1•Else•s=s(n-1)*n•EndIf•EndFunction•PrivateSubform_Click()'调用递归函数，显示结果•Prints(5)=;s(5)•EndSub递归法的实现•有人养了一对兔子，这对兔子以后每月生一对兔子，新生兔子从第三个月开始，也是每月生一对兔子，问12个月后这人有多少对新生兔子？问题分析这个问题是公元前13世纪意大利数学家斐波那契的名著《算盘书》里的问题。图中每个色块表示一对兔子，其中白色色块表示新生兔子。从图中可以发现，每月新生兔子的对数为：1,1,2,3,5……从第三个月起，当月新生兔子数为前两月新生兔子数之和。这个数列在数学上被称做“斐波那契数列”。程序实现•这个问题如果不用递归法解决，其参考代码如下：•PrivateFunctionHares(ByValintMonthAsInteger)AsInteger•DimiAsInteger•DimintCurMonAsInteger'当前月新生兔子对数•DimintPreMon1AsInteger'前一个月新生兔子对数•DimintPreMon2AsInteger'前两个月新生兔子对数•'前两个月分别为1对•intPreMon1=1•intPreMon2=1•'从第3月起,新生兔子为前两月之和•Fori=3TointMonth•intCurMon=intPreMon2+intPreMon1•intPreMon1=intPreMon2•intPreMon2=intCurMon•Next•Hares=intCurMon•EndFunction用递归法实现。参考代码如下：•PublicFunctionS(NAsInteger)AsInteger•IfN=1OrN=2Then•S=1•Else•S=S(N－1)+S(N－2)•EndIf•EndFunction年龄问题•有5个人做在一起，问第5个人多大了。他说比第四个人大2岁，问第四个人多大了，他说比第三个人大2岁，问第三个人多大了，他说比第二个人大2岁，问第二个人多大了，他说比第一个人大2岁，最后问第一个人，他说他10岁了。请问第5个人多大了？递归法的归纳1：•递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。递归算法解决问题的特点：(1)递归就是在过程或函数里调用自身。(2)在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。(3)递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序递归法的归纳2：递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半)；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。