VB递归算法讲解.ppt

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 AsLongIfn 1Thens 1Elses s n 1 nEndIfEndsub PublicFunctions nAsInteger AsLongIfn 1Thens 1Elses s n 1 nEndIfEndFunction 比较两个数的大小 PublicFunctionmax nAsInteger AsIntegerIfa bThenmax aElsemax bEndIfEndFunctionPrivateSubcommand Click 调用递归函数 显示结果Printmax 3 5 EndSub 基本思想 把规模大的 较难解决的问题变成规模较小的 易解决的同一问题 规模较小的问题又变成规模更小的问题 并且小到一定的程度直到可以直接得出它的解 从而得到原来问题的解 注意 必须要有一个结束递归的条件 不得无限递归 分析步骤 1 决定问题规模的参数 2 问题的边界条件及边界值 3 解决问题的通式 例 计算一个数的阶乘 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 递归函数求5 PublicFunctions nAsInteger AsLongIfn 1Thens 1Elses s n 1 nEndIfEndFunctionPrivateSubform Click 调用递归函数 显示结果Print s 5 s 5 EndSub 递归法的实现 有人养了一对兔子 这对兔子以后每月生一对兔子 新生兔子从第三个月开始 也是每月生一对兔子 问12个月后这人有多少对新生兔子 问题分析 这个问题是公元前13世纪意大利数学家斐波那契的名著 算盘书 里的问题 图中每个色块表示一对兔子 其中白色色块表示新生兔子 从图中可以发现 每月新生兔子的对数为 1 1 2 3 5 从第三个月起 当月新生兔子数为前两月新生兔子数之和 这个数列在数学上被称做 斐波那契数列 程序实现 这个问题如果不用递归法解决 其参考代码如下 PrivateFunctionHares ByValintMonthAsInteger AsIntegerDimiAsIntegerDimintCurMonAsInteger 当前月新生兔子对数DimintPreMon1AsInteger 前一个月新生兔子对数DimintPreMon2AsInteger 前两个月新生兔子对数 前两个月分别为1对intPreMon1 1intPreMon2 1 从第3月起 新生兔子为前两月之和Fori 3TointMonthintCurMon intPreMon2 intPreMon1intPreMon1 intPreMon2intPreMon2 intCurMonNextHares intCurMonEndFunction 用递归法实现 参考代码如下 PublicFunctionS NAsInteger AsIntegerIfN 1OrN 2ThenS 1ElseS S N 1 S N 2 EndIfEndFunction 年龄问题 有5个人做在一起 问第5个人多大了 他说比第四个人大2岁 问第四个人多大了 他说比第三个人大2岁 问第三个人多大了 他说比第二个人大2岁 问第二个人多大了 他说比第一个人大2岁 最后问第一个人 他说他10岁了 请问第5个人多大了 递归法的归纳1 递归算法的实质 是把问题转化为规模缩小了的同类问题的子问题 然后递归调用函数 或过程 来表示问题的解 递归算法解决问题的特点 1 递归就是在过程或函数里调用自身 2 在使用递增归策略时 必须有一个明确的递归结束条件 称为递归出口 3 递归算法解题通常显得很简洁 但递归算法解题的运行效率较低 所以一般不提倡用递归算法设计程序 递归法的归纳2 递归算法所体现的 重复 一般有三个要求 一是每次调用在规模上都有所缩小 通常是减半 二是相邻两次重复之间有紧密的