3.5 用递归法解决问题 黄学鸿
故事 “从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”…………
这个故事有什么特点? 自己调用自己 如果在一个函数中,它自己调用了自己,这种现象叫递归调用。 如果A函数调用B函数,B函数又反过来调用A函数,那这种现象也叫做递归调用。 如果一个函数在定义时,直接或间接的调用了自己,这种算法在程序设计中统称为递归法。
Abs()、len()、date()、sqr()、msgbox()等 自定义函数 递归法一般需要定义函数来实现。 Abs()、len()、date()、sqr()、msgbox()等 虽然VB为我们提供了大量的标准函数,但我们在实际应用时难免有时还是找不到合意的,那就只有自己解决了,这样为了一个特定的任务而编出来的函数叫自定义函数。
二、自定义函数的作用 1、可以方便的把较为复杂的问题分解成若干个小问题去处理。(公司里就是采用这中模式的。) 2、使程序结构清晰,层次分明,增强了程序的可读性。
一、标准函数 VB给我们提供了一些标准函数,我们不用了解这些函数如何求出来的,只管直接调用它们,挺方便的。如正弦函数,余弦函数,算术平方根......有了这些函数,我们觉得很省事。如:求1加到100的算术平方根这个程序我们可以这样编写: 例1 dim I as integer, s as single s=0 for i=1 to 100 do s=s+sqr(i) next i writeln('s=',s)
在这个程序里,我们直接用到了求平方根函数,至于sqr(1),sqr(2)如何求出来的我们不需过问,只管直接用它的结果便是了。 象这样,VB给我们提供的,我们不用了解这些函数如何求出来的,只管直接调用它们的这类函数叫做标准函数。 二、用户自定义函数 我们来看看下面一个例子:求:1!+2!+3!+...+10!=? 如果要编写程序,我们看到求阶乘的操作要执行10次,只不过每次所求的数不同。我们想:不至于编写10遍求阶乘的程序吧。我们希望有一个求阶乘的函数,假设为JS(X),那么我们就可以这样求这道题了:
例2 dim I as integer, j as integer dim s as integer s=0 for i=1 to 10 do s=s+js(i) next i writeln('s=',s) 现在的问题是:VB没提供JS(X)这样一个标准函数,这个程序是通不过的。如果是PASCAL的标准函数,我们可以直接调用,如前面的sqr(i),而PASCAL提供给我们的可供直接调用的标准函数不多。没关系,我们编写自己的函数!
在VB中,自定义函数形式如下: 三、函数编写 [Public|Private] Function <函数名称> ([参数列表]) [As 类型] 局部常量、变量定义 语句组 函数名称=返回值 End Function Public(公共的)-----全局变量,指在所有程序(包括主程序和过程)中都可以使用的内存变量. Private(私人的)-----局部变量,用private语句声明的变量可被本窗体/模块的任何过程访问,但其他模块却不能访问该变量. 参数列表: [ByVal | ByRef] 变量名 [( )] [As 类型] 表示该参数按地址传递 会直接改变原来的变量值 表示该参数按值传递 不会修改变量原来的值
例3 编写一求阶乘的函数。 我们给此函数取一名字就叫JS。 fUNCTION js(n as integer) as integer dim I as integer, s as integer s=1 for i=1 to n do s=s*i next i js=s end
自定义函数的调用,可以有三种格式: 变量=函数名称(参数) Call 函数名称(参数) 函数名称 参数
Private Function daxiao(a As Integer, b As Integer) Dim t As Integer If a < b Then t = a a = b b = t End If End Function Private Sub Command1_Click() Dim a As Integer, b As Integer a = 5 b = 9 Call daxiao(a, b) Print "a="; a, "b="; b End Sub Private Sub Command1_Click() Dim a As Integer, b As Integer a = 5 b = 9 Daxiao a, b Print "a="; a, "b="; b End Sub
子过程 函数 子过程和函数的本质是一样的,在VB中往往将函数看做特殊的子过程 变量=函数名称(参数) Call 函数名称(参数) [Public|private] sub <子过程名称> ([参数列表]) 局部常量 变量定义 过程语句组 End sub 子过程和函数的本质是一样的,在VB中往往将函数看做特殊的子过程 子过程与函数的区别: 关键字:函数(Function) 子过程(sub) 返回值:函数(可以有) 子过程(无) 调用格式: 变量=函数名称(参数) Call 函数名称(参数) 函数名称 参数 函数 子过程 Call 函数名称(参数) 函数名称 参数
递归调用算法 使用递归算法必须要满足以下的递归条件: (1)存在递归结束条件及结束时的值 (2)能用递归形式表示,且递归向终止条件发展
兔子繁殖问题 有人养了一对兔子,这对兔子以后每月生一对兔子,新生兔子从第三个月开始,也是每月生一对兔子.从第三个月起,当月新生兔子数为前两月新生兔子数之和.问12个月后这人有多少对新生兔子?
问题分析 1月 2月 3月 4月 5月
图3-25 函数递归调用关系 Recursion(5)=Recursion(4)+Recursion(3) 图3-25 函数递归调用关系 Recursion(5)=Recursion(4)+Recursion(3) Recursion(4)=Recursion(3)+Recursion(2) Recursion(3)=Recursion(2)+Recursion(1) Recursion(2)=1 Recursion(1)=1
关于递归的例子: 例1:假设有如下sub过程: Sub s(x as single,y as single) t=x x=t/y y=t mod y End sub Private sub command1_click() dim a as single dim b as single a=5 b=4 s a,b 函数名称 参数 Print a,b
例2:在窗体上画一个名称为command1的命令按钮,然后编写如下通用过程和命令按钮的事件过程: Private function fun(byval m as integer) If m mod 2 =0 then fun=2 else fun=1 end if End function Private sub command1_click() dim I as integer,s as integer s=0 For I=1 to 5 s=s+fun(I) Next I Print s End sub
例3:单击命令按钮时,下列程序的执行结果为( ) 例3:单击命令按钮时,下列程序的执行结果为( ) Private sub command1_click() Dim x as integer,y as integer X=12:y=32 Call proc(x,y) Print x;y End sub Public sub proc(n as integer,by val m as integer) N=n mod 10 A、1232 B、232 C、23 D、123