高中信息技术《递归算法与递归程序》课件

递归算法与递归程序这幅图中，蕴含了一个的神奇的故事，你能讲出这个故事吗？从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事：老和尚说：“从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事：老和尚说：“从前有座山，山里有座庙…这个故事有什么独特之处？故事之中嵌套了故事本身，循环往复，无休无止事例1：做个游戏，看图讲故事事例2：想像一下，当你身处一个两面都是镜子的空间里，你会看到什么样的景象？镜中有像，像中有镜，层层叠叠，无穷无尽事例1中，“从前有座山…”中故事讲述了故事本身。事例2中，A镜中有B镜的镜像，B镜的镜像中又有A镜的镜像，镜像互相映照，层层叠叠。故事

镜子A

镜子B在程序设计中，运用递归思想设计的算法，我们称之为“递归算法”。那么，递归算法是怎样实现的，如何运用递归算法来解决我们生活中的实际问题呢？今天这节课，我们就来共同探究递归算法与递归程序，揭开递归算法的神秘面纱。这种事物直接或者间接调用自身的现象，我们称之为“递归”。

著名的意大利数学家斐波那契在他的著作《算盘书》中提到了这样一个问题：有人年初养了一对小兔子，这对小兔子一个月后就可以长成大兔子，而大兔子每个月都会生出一对小兔子，问到年底时一共有多少对兔子?。。。？问题1：斐波那契的兔子问题兔子问题分析：1月2月3月4月5月6月7月8月9月10月11月12月小兔大兔合计每月大兔数=下月小兔数每月兔子总数=下月大兔数1月2月3月4月5月6月想一想：每月大兔数与下月小兔数是什么关系？每月兔子总数与下月大兔数又是什么关系？11235512315534144895534211388511211321345589231381

用列表的方法，我们很容易地解决了问题，但仔细观察表格中的数据，我们会发现随着月份的增长兔子的数目增长的越来越快，如果时间再长的话用列表的方法就会越来越困难。试想一下，你愿意用列表的方法求出5年后兔子的数目吗？所以，我们需要寻找更简便更一般的方法。想一想：还有什么更好的方法？编程求解1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321347589合计11235813213455891441.分析问题：仔细研究表中的数据，你有什么发现？从第3个月开始，每月兔子数等于前两个月的兔子数之和每个月的兔子总数=小兔数+大兔数=上个月大兔数+上个月兔子总数=上上个月兔子总数+上个月兔子总数

为什么？假设第N个月的兔子数目是F(N)，那么兔子问题的求解可以描述为一个函数：F(1)=F(2)=1N<3F(N)=F(N-1)+F(N-2)N>=3观察：这个函数有什么特点？函数自己调用了自己（递归）1.分析问题（用函数描述问题的求解）：F(4)=F(3)+F(2)F(5)=F(4)+F(3)F(6)=F(5)+F(4)F(3)=F(2)+F(1)F(4)=F(3)+F(2)F(3)=F(2)+F(1)F(3)=F(2)+F(1)F(1)=F(2)=1N<3F(N)=F(N-1)+F(N-2)N>=3递推回归

递归算法实质是把问题转化为规模缩小了的同类问题的子问题，然后通过函数（或过程）重复的层层自我调用（递归调用）来描述问题的解答。2.设计算法（定义函数，调用函数）：问题需求：求第N个月的兔子数目是F(N)Step1:定义函数f(n)（用函数描述问题的求解）

当N<3时，f(n)=1；当N>=3时，f(n)=f(n-1)+F(N-2)Step2:输入月份nStep3:输出f(n)（调用定义的函数f(n)）主程序Sub流程图：自定义函数F(N)流程图：3.编写程序:定义函数：FunctionF(ByValNAsInteger)AsLongIfN<3thenF=1elseF=F(N-1)+F(N-2)EndFunction自定义函数的定义格式:Function函数名称(参数列表)[As类型]语句组EndFunction

子过程的定义格式:PrivateSub子过程名称(参数列表)过程语句组EndSub

调用自定义函数的格式：变量=函数名称(参数)

定义子过程：PrivateSubCommand1_Click()N=Val(Text1.Text)Label3.Caption=F(N)EndSub1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321347589合计1123581321345589144打开ep1.frm文件，输入程序，运行并测试结果：4.运行调试，测试结果：任务1:尝试用递归算法编写程序，解决斐波那契的兔子问题。打开ep1.frm窗体文件，补充程序代码并运行调试，测试结果。1.递归算法是如何实现的？递归算法的实质是什么？2.运用递归算法编程解决问题的一般过程与方法？3.递归算法解决问题有什么特点？交流与讨论：1.递归算法的实质及实现方法：递归算法实质是把问题转化为规模缩小了的同类问题的子问题，然后通过函数（或过程）重复的层层自我调用（递归调用）来描述问题的解答。课堂小结：3.递归算法解决问题的特点：（1）问题描述简洁，结构清晰，易于理解；（2）必须有一个明确的递归结束条件，称为递归出口，无结束条件（出口）的递归调用不能正常结束（溢出或者死循环）。（3）耗费计算机资源（占用内存空间）大，效率较低2.运用递归算法编程解决问题的一般过程与方法：（1）定义递归函数（或者过程）（用递归函数描述问题的求解）；（2）调用自定义函数（或者过程），求得结果问题2.数学上对正整数n的阶乘的定义是1n=0n!=1×2×3×…×n,n>0

任务2:打开ep2.frm，将程序补充完整，实现求任意正整数N的阶乘n!=1×2×3×…×(N-1)×n(N-1)!=1×2×3×…×(N-1)…1!=1×10!=1

用函数F(N)描述N!1n=0

F(N)=n>0问题3.在计算机内部是用加法运算来求乘法运算结果的。试编写一个程序实现求出两个正整数M与N相乘的结果，代码中不能出现乘法运算。

任务3:打开ep3.frm，将程序补充完整，实现用加法运算求正整数M与N的乘积。M×N=M+M+…+M(N个M）M×(N-1)=M+M+…+M(N-1个M）

…

M×2=M+M

M×1=M

用函数F(N)描述N!mn=1

F(N)=n>1用函数F(N)描述N!mn=1

F(N)=n>1任务4:打开ep4.frm，将程序代码补充完整，实现求从比萨斜塔落下的小球N次着地后经过的垂直距离.第1次着地，F(1)=54.5第2次着地，F(2)=54.5+54.5/2=81.75第3次着地，F(3