VB递归算法讲解

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.5,用递归法解决问题,什么是递归法,从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事，讲什么呢？,从前有座山，山里有座庙，,很久以前，有一则古老而有趣的故事，流传至今：,蕴含了递归思想,递归法包括,2,种情况：,函数自己调用自己,两个函数之间相互调用,如果一个函数在定义时，直接或间接地调用了自己，这种算法在程序设计中统称为,递归法,。,函数,是为了实现某种功能而编写的一段相对独立的程序。,自定义函数,是指我们自己编写的函数。,标准函数,自定义函数,Abs( ),、,len( ),、,mid( ),、,chr( ),、,asc( ),自定义函数,:,在,VB,中，自定,义,函数,形式,如下：,Public,|,Private,Function, (,参数,列,表,) ,As,类,型,局部常量,、,变量,定,义,语,句,组,函,数,名,称,=,返,回值,End Function,自定,义,函数,的,调,用，可以有,三种,格式,：,变量,=,函,数,名,称（参数）,Call,函,数,名,称（参数）,函,数,名,称,参数,子过程的定义,Public,|,private,function, (,参数列表,) as,类型,局部常量、变量定义,语句组,函数名称,=,返回值,End function,public,|,private,sub, (,参数列表,),局部常量、变量定义,过程语句组,End sub,自定义函数：,子过程的定义：,private sub s(n As Integer) As Long,If n = 1 Then,s =1,Else,s =s(n-1)*n,End If,End sub,Public Function s(n As Integer) As Long,If n = 1 Then,s =1,Else,s =s(n-1)*n,End If,End Function,比较两个数的大小,Public Function max(n As Integer) As Integer,If ab Then,max=a,Else,max=b,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,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,递归法的实现,有,人,养,了一对,兔,子,，这对,兔,子,以后,每,月,生,一对,兔,子,，,新生,兔,子,从,第三个,月,开始，也是,每,月,生,一对,兔,子,，问,12,个,月,后这,人,有多少对,新生,兔,子,？,问题分析,这,个,问题是,公元前,13,世,纪,意大,利,数,学,家,斐波,那,契,的名,著,算,盘,书,里,的问题。图中,每,个色块表示,一对,兔,子,，,其,中,白,色色块表示新生,兔,子,。从图中可以,发现,，,每,月,新生,兔,子,的对,数,为：,1,1,2,3,5,从,第三个,月,起，当,月,新生,兔,子,数,为,前,两,月,新生,兔,子,数,之,和。这,个数,列,在,数,学上,被,称做,“,斐波,那,契,数,列,”,。,程序实现,这,个,问题如,果,不用,递归,法解决，,其,参,考代码,如下：,Private Function Hares,(,ByVal intMonth As Integer,),As Integer,Dim i As Integer,Dim intCurMon As Integer,当,前月新,生,兔,子,对数,Dim intPreMon1 As Integer,前,一个,月新,生,兔,子,对数,Dim intPreMon2 As Integer,前,两个,月新,生,兔,子,对数,前,两个,月,分,别,为,1,对,intPreMon1 = 1,intPreMon2 = 1,从第,3,月起,新,生,兔,子,为,前,两,月,之,和,For i = 3 To intMonth,intCurMon = intPreMon2,+,intPreMon1,intPreMon1 = intPreMon2,intPreMon2 = intCurMon,Next,Hares = intCurMon,End Function,用,递归,法,实现,。,参,考代码,如下：,Public Function S,(,N As Integer,),As Integer,If N = 1 Or N= 2 Then,S = 1,Else,S = S,(,N,1,),+ S,(N,2,),End If,End Function,年龄问题,有,5,个人做在一起，问第,5,个人多大了。他说比第四个人大,2,岁，问第四个人多大了，他说比第三个人大,2,岁，问第三个人多大了，他说比第二个人大,2,岁，问第二个人多大了，他说比第一个人大,2,岁，最后问第一个人，他说他,10,岁了。请问第,5,个人多大了？,递归法的归纳,1,：,递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数,(,或过程,),来表示问题的解。,递归算法解决问题的特点：,(1),递归就是在过程或函数里调用自身。,(2),在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。,(3),递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序,递归法的归纳,2,：,递归算法所体现的“重复”一般有三个要求：,一是每次调用在规模上都有所缩小,(,通常是减半,),；,二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备,(,通常前一次的输出就作为后一次的输入,),；,三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的,(,以规模未达到直接解答的大小为条件,),，无条件递归调用将会成为死循环而不能正常结束。,