VB递归算法讲解(课堂PPT)

1,3.5用递归法解决问题,2,什么是递归法,从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事，讲什么呢？从前有座山，山里有座庙，,很久以前，有一则古老而有趣的故事，流传至今：,蕴含了递归思想,3,递归法包括2种情况：,函数自己调用自己,两个函数之间相互调用,如果一个函数在定义时，直接或间接地调用了自己，这种算法在程序设计中统称为递归法。,4,函数是为了实现某种功能而编写的一段相对独立的程序。,自定义函数是指我们自己编写的函数。,标准函数自定义函数,Abs()、len()、mid()、chr()、asc(),5,自定义函数:,在VB中，自定义函数形式如下：Public|PrivateFunction(参数列表)As类型局部常量、变量定义语句组函数名称=返回值EndFunction自定义函数的调用，可以有三种格式：变量=函数名称（参数）Call函数名称（参数）函数名称参数,6,子过程的定义,Public|privatefunction(参数列表)as类型局部常量、变量定义语句组函数名称=返回值Endfunction,public|privatesub(参数列表)局部常量、变量定义过程语句组Endsub,自定义函数：,子过程的定义：,privatesubs(nAsInteger)AsLongIfn=1Thens=1Elses=s(n-1)*nEndIfEndsub,PublicFunctions(nAsInteger)AsLongIfn=1Thens=1Elses=s(n-1)*nEndIfEndFunction,7,比较两个数的大小,PublicFunctionmax(nAsInteger)AsIntegerIfabThenmax=aElsemax=bEndIfEndFunctionPrivateSubcommand_Click()调用递归函数，显示结果Printmax(3,5)EndSub,8,基本思想:,把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定的程度直到可以直接得出它的解，从而得到原来问题的解。注意：必须要有一个结束递归的条件，不得无限递归。,9,分析步骤：,1.决定问题规模的参数。2.问题的边界条件及边界值。3.解决问题的通式。,10,例:计算一个数的阶乘,1!=1f(1)=12!=1*2f(2)=f(1)*23!=1*2*3f(3)=f(2)*34!=1*2*3*4f(4)=f(3)*45!=1*2*3*4*5f(5)=f(4)*5.n!=1*2*3*4*5*.*nf(n)=f(n-1)*n,11,递归函数求5！,PublicFunctions(nAsInteger)AsLongIfn=1Thens=1Elses=s(n-1)*nEndIfEndFunctionPrivateSubform_Click()调用递归函数，显示结果Prints(5)=;s(5)EndSub,12,递归法的实现,有人养了一对兔子，这对兔子以后每月生一对兔子，新生兔子从第三个月开始，也是每月生一对兔子，问12个月后这人有多少对新生兔子？,13,问题分析,这个问题是公元前13世纪意大利数学家斐波那契的名著算盘书里的问题。图中每个色块表示一对兔子，其中白色色块表示新生兔子。从图中可以发现，每月新生兔子的对数为：1,1,2,3,5从第三个月起，当月新生兔子数为前两月新生兔子数之和。这个数列在数学上被称做“斐波那契数列”。,14,程序实现,这个问题如果不用递归法解决，其参考代码如下：PrivateFunctionHares(ByValintMonthAsInteger)AsIntegerDimiAsIntegerDimintCurMonAsInteger当前月新生兔子对数DimintPreMon1AsInteger前一个月新生兔子对数DimintPreMon2AsInteger前两个月新生兔子对数前两个月分别为1对intPreMon1=1intPreMon2=1从第3月起,新生兔子为前两月之和Fori=3TointMonthintCurMon=intPreMon2+intPreMon1intPreMon1=intPreMon2intPreMon2=intCurMonNextHares=intCurMonEndFunction,15,用递归法实现。参考代码如下：,PublicFunctionS(NAsInteger)AsIntegerIfN=1OrN=2ThenS=1ElseS=S(N1)+S(N2)EndIfEndFunction,16,年龄问题,有5个人做在一起，问第5个人多大了。他说比第四个人大2岁，问第四个人多大了，他说比第三个人大2岁，问第三个人多大了，他说比第二个人大2岁，问第二个人多大了，他说比第一个人大2岁，最后问第一个人，他说他10岁了。请问第5个人多大了？,17,递归法的归纳1：,递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。递归算法解决问题的特点：(1)递归就是在过程或函数里调用自身。(2)在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。(3)递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序,18,递归法的归纳2：,递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半)；二是相邻两次重复之间有紧密的