用递归法解决问题.ppt

1、3.5 用递归法解决问题,徐州第二十六中学 朱九妹,“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座

2、庙,庙里有个老和尚给小和尚讲故事,讲什么呢? 从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”,故事,这个故事有什么特点？,自己调用自己,如果在一个函数中，它自己调用了自己，这种现象叫递归调用。,如果A函数调用B函数，B函数又反过来调用A函数，那这种现象也叫做递归调用。,如果一个函数在定义时，直接或间接的调用了自己，这种算法在程序设计中统称为递归法。,递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。,子程序中定义递归调用。一般格式为：,if 边界条件

3、 1 成立 then 赋予边界值 1 elseif 边界条件 2 成立 then 赋予边界值 2 else 调用解决问题的通式 endif,自定义函数,递归法一般需要定义函数来实现。这里所讲的函数是自定义函数。,虽然VB为我们提供了大量的标准函数，但我们在实际应用时难免有时还是找不到合意的，那就只有自己解决了，这样为了一个特定的任务而编出来的函数叫自定义函数。,Abs( )、len( )、date( )、sqr( )、msgbox( )等,二、自定义函数的作用 1、可以方便的把较为复杂的问题分解成若干个小问题去处理。(公司里就是采用这中模式的。) 2、使程序结构清晰，层次分明，增强了程序的可读

4、性。,一、标准函数 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 print “s=”;s,在这个程序里，我们直接用到了求平方根函数，至于sqr（1），sqr（2）如何求出来的我们不需过问，只管直接用它的结果便是了。 象这样，VB给我们提供的，我们不用了解这些函数如何求出来的，只管直接调

5、用它们的这类函数叫做标准函数。,二、用户自定义函数 我们来看看下面一个例子：求：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 print “s=“;s 现在的问题是：VB没提供JS（X）这样一个标准函数，这个程序是通不过的。如果是PASCAL的标准函数，

6、我们可以直接调用，如前面的sqr(i)，而PASCAL提供给我们的可供直接调用的标准函数不多。没关系，我们编写自己的函数！,三、函数编写,在VB中，自定义函数形式如下：,PublicPrivate Function (参数列表)As 类型 局部常量、变量定义 语句组 函数名称返回值 End Function,Public(公共的)-全局变量,指在所有程序（包括主程序和过程）中都可以使用的内存变量,Private(私人的)-局部变量,用private语句声明的变量可被本窗体模块的任何过程访问，但其他模块却不能访问该变量,参数列表： ByVal | ByRef 变量名 ( ) As 类型,表示该参

7、数按值传递 不会修改变量原来的值,表示该参数按地址传递 会直接改变原来的变量值,例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 函数名称(参数) 格式三：函数名称 参数,使用递归算法大致结构为：,（）递归出口 （）递归体 一个递归算法，当其问题求解的规模越来越小时必定有一个递归出口，就是不再递归调用的语句。递归体则是每次递归时执行的语句序列。,递归调用算法,例如：编写递归函数求5！的值,Public Function s ( n As Integer) As Long If n=1 Then s=1 Else s=n*s(n-1) End if End Function Private Sub Form_Click( ) Pr