3.5.3递归法的实现.pptx

3 5用递归法解决问题 邯郸市第四中学付新良 教育科学出版社普通高中课程标准实验教科书 算法与程序设计 选修 3 5 1什么是递归法 很久以前 有一则古老而有趣的故事 流传至今 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 从前有座山 山里有座庙 蕴含了递归的思想 3 5 1什么是递归法 函数是为了实现某种功能而编写的一段相对独立的程序 函数A 函数A 函数B 3 5 2什么是自定义函数 在VB中 自定义函数形式如下 Public Private Function 参数列表 As类型 局部常量 变量定义语句组函数名称 返回值EndFunction 自定义函数的调用 可以有三种格式 变量 函数名称 参数 Call函数名称 参数 函数名称参数 3 5 2什么是自定义函数 子过程的定义 Public private function 参数列表 as类型 局部常量 变量定义语句组函数名称 返回值Endfunction 实例1 PublicFunctions nAsInteger AsLongIfn 1Thens 1Elses s n 1 nEndIfEndFunction 3 5 2什么是自定义函数 子过程的定义 public private sub 参数列表 局部常量 变量定义过程语句组Endsub 实例2 privatesubs nAsInteger AsLongIfn 1Thens 1Elses s n 1 nEndIfEndsub 3 5 2什么是自定义函数 比较两个数的大小 PublicFunctionmax aAsInteger bAsInteger AsIntegerIfa bThenmax aElsemax bEndIfEndFunctionPrivateSubcommand Click 调用递归函数 显示结果Printmax 3 5 EndSub 函数名 函数参数 调用函数 3 5 2什么是自定义函数 把规模大的 较难解决的问题变成规模较小的 易解决的同一问题 规模较小的问题又变成规模更小的问题 并且小到一定的程度直到可以直接得出它的解 从而得到原来问题的解 注意 必须要有一个结束递归的条件 不得无限递归 1 决定问题规模的参数 2 问题的边界条件及边界值 3 解决问题的通式 基本思想 分析步骤 3 5 2什么是自定义函数 计算一个数的阶乘 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 3 5 2什么是自定义函数 递归函数求5 阶乘 PublicFunctions nAsInteger AsLongIfn 1Thens 1Elses s n 1 nEndIfEndFunctionPrivateSubform Click 调用递归函数 显示结果Print s 5 s 5 EndSub 函数名 函数参数 调用函数 3 5 3递归法的实现 有人养了一对兔子 这对兔子以后每月生一对兔子 新生兔子从第三个月开始 也是每月生一对兔子 问12个月后这人有多少对新生兔子 3 5 3递归法的实现 问题分析 这个问题是公元前13世纪意大利数学家斐波那契的名著 算盘书 里的问题 图中每个色块表示一对兔子 其中白色色块表示新生兔子 从图中可以发现 每月新生兔子的对数为 1 1 2 3 5 从第三个月起 当月新生兔子数为前两月新生兔子数之和 这个数列在数学上被称做 斐波那契数列 3 5 3递归法的实现 问题分析 这个问题如果不用递归法解决 其参考代码如下 PrivateFunctionHares ByValintMonthAsInteger AsIntegerDimiAsIntegerDimintCurMonAsInteger 当前月新生兔子对数DimintPreMon1AsInteger 前一个月新生兔子对数DimintPreMon2AsInteger 前两个月新生兔子对数intPreMon1 1 前两个月分别为1对intPreMon2 1Fori 3TointMonth 从第3月起 新生兔子为前两月之和intCurMon intPreMon2 intPreMon1intPreMon1 intPreMon2intPreMon2 intCurMonNextHares intCurMonEndFunction 3 5 3递归法的实现 问题分析 用递归法实现 参考代码如下 PublicFunctionS NAsInteger AsIntegerIfN 1OrN 2ThenS 1ElseS S N 1 S N 2 EndIfEndFunction 3 5 3递归法的实现 汉诺塔递归分析 汉诺塔 又称河内塔 问题是源于印度一个古老传说的益智玩具 大梵天创造世界的时候做了三根金刚石柱子 在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上 并且规定 在小圆盘上不能放大圆盘 在三根柱子之间一次只能移动一个圆盘 3 5 3递归法的实现 抽象为数学问题 如下图所示 从左到右有A B C三根柱子 其中A柱子上面有从小叠到大的n个圆盘 现要求将A柱子上的圆盘移到C柱子上去 期间只有一个原则 一次只能移到一个盘子且大盘子不能在小盘子上面 求移动的步骤和移动的次数 3 5 3递归法的实现 软件演示 3 5 3递归法的实现 程序代码 PrivateSubCommand1 Click Me MousePointer vbHourglass 注意 盘子的数量不要大于10 CallHanoi 5 A B C Me MousePointer vbNormalEndSubPrivateFunctionHanoi ByValnAsInteger ByValstrOneAsString ByValstrTwoAsString ByValstrThreeAsString Ifn 1ThenCallMoveOne strOne strThree ElseCallHanoi n 1 strOne strThree strTwo CallMoveOne strOne strThree CallHanoi n 1 strTwo strOne strThree EndIfEndFunctionPrivateFunctionMoveOne ByValstrOneAsString ByValstrAnotherAsString PrintstrOne strAnotherEndFunction 3 5 3递归法的实现 本章练习 Quiz ClicktheQuizbuttontoeditthisobject 3 5 3递归法的实现 递归算法的实质 是把问题转化为规模缩小了的同类问题的子问题 然后递归调用函数 或过程 来表示问题的解 递归算法解决问题的特点 1 递归就是在过程或函数里调用自身 2 在使用递增归策略时 必须有一个明确的递归结束条件 称为递归出口 3 递归算法解题通常显得很简洁 但递归算法解题的运行效率较低 所以一般不提倡用递归算法设计程序 递归法归纳总结一 3 5 3递归法的实现 递归算法所体现的 重复 一般有三个要求 一是每次调用在规