高中信息技术：递归算法-PPT名师优质课获奖市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,递 归 算 法,第1页,什么是递归算法,?,递归算法：是一个直接或者间接地调用本身算法。在计算机编写程序中，递归算法对处理一大类问题是十分有效，它往往使算法描述简练而且易于了解。,第2页,斐波那契兔子问题,某人有一对兔子喂养在围墙中，假如它们每个月生一对兔子，且新生兔子在第二个月后也是每个月生一对兔子，问一年后围墙中共有多少对兔子。,第3页,分析,:,第一个月是最初一对兔子生下一对兔子，围墙内共有两对兔子。第二个月仍是最初一对兔子生下一对兔子，共有,3,对兔子。到第三个月除最初兔子新生一对兔子外，第一个月生兔子也开始生兔子，所以共有,5,对兔子。继续推下去，第,12,个月时最终共有对,377,对兔子。每个月兔子总数可由前两个月兔子数相加而得。,第4页,算法,:,输入计算兔子月份数：,n,If n 3 Then c=1 Else a=1:b=1,i=3,c=a+b,：,a=b,：,b=c,i=i+1,假如,in,则返回,结束,第5页,Private Sub Command1_Click(),n=Val(Text1.Text),If n 3 Then c=1 Else a=1:b=1,For i=3 To n,c=a+b,a=b,b=c,Next i,Text2.Text=,第,&n&,月兔子数目是：,&c,End Sub,第6页,开动脑筋：,我们有没有更简单方法处理该问题呢？,第7页,(1),分析问题,我们能够依据题意列出表来处理这个问题：,兔子问题分析表,第8页,交流,:,仔细研究兔子问题分析表，你有些什么发觉？每一个月份大兔数、小兔数与上一个月数字有什么联络，能必定这个规律吗？,第9页,(2),设计算法。,“,兔子问题,”,很轻易列出一条递推式而得到处理。假设第,N,个月兔子数目是,F(N),，我们有：,这是因为每个月大兔子数目一定等于上月兔子总数，而每个月小兔子数目一定等于上月大兔子数目,(,即前一个月兔子数目,),。,由上述递推式我们能够设计出递归程序。递归程序特点是独立写出一个函数,(,或子过程,),，而这个函数只对极简单几个情况直接给出解答，而在其余情况下经过重复调用本身而把问题归结到最简单情况而得到解答。,第10页,知识复习：,自定义函数定义格式,:,Function procedurename(arguments)As type,Statements,End Function,其中,procedurename,是函数名，,arguments,是函数中参数表，,type,是函数返回值数据类型，,表示可有可无部分，,statements,是过程中代码,调用函数格式：,procedurename(arguments),第11页,(3),编写程序,窗体中开设一个文本框,Text1,用于填人月数,N,，设置命令框,Commandl,，点击它即执行程序求出第,N,月兔子数。然后用文本框,Text2,输出答案。,第12页,依据递推式能够写出递归程序以下：,Function Fib(ByVal N As Integer)As Long,If N 3 Then Fib=1 Else Fib=Fib(N-1)+Fib(N-2),End Function,Private Sub Command1_Click(),N=Val(Text1.Text),Text2.Text=,第,&N&,月兔子数目是：,&Fib(N),End Sub,第13页,(4),调试程序,因为这个算法效率不高，提议在调试程序时月份数不要大于,40,。,第14页,知识迁移：,(1),利用递归方法编写一求,N,阶乘。,分析：,依据,N!=N*(N-1)*(N-2)*(N-3)*,*3*2*1,能够推出以下式子：,第15页,Function F(ByVal n As Integer)As Long,If n=1 Then F=1 Else F=n*F(n-1),End Function,Private Sub Form_Click(),Dim n As Integer,n=Val(InputBox(,请输入正整数,N,：,求,N,阶乘,),Print,输入正整数是,;n;,Print,，阶乘是,;F(n),End Sub,第16页,本节小结：,递归算法特点,递归过程普通经过函数或子过程来实现。,递归算法：在函数或子过程内部，直接或者间接地调用自己算法。,递归算法实质：是把问题转化为规模缩小了同类问题子问题。然后递归调用函数,(,或过程,),来表示问题解。,第17页,递归算法处理问题特点：,(1),递归就是在过程或函数里调用本身。,(2),在使用递增归策略时，必须有一个明确递归结束条件，称为递归出口。,(3),递归算法解题通常显得很简练，但递归算法解题运行效率较低。所以普通不提倡用递归算法设计程序。,(4),在递归调用过程当中系统为每一层返回点、局部量等开辟了栈来存放。递归次数过多轻易造成栈溢出等。所以普通不提倡用递归算法设计程序。,第18页,递归算法所表达,“,重复,”,普通有三个要求：,一是每次调用在规模上都有所缩小,(,通常是减半,),；,二是相邻两次重复之间有紧密联络，前一次要为后一次做准备,(,通常前一次输出就作为后一次输入,),；,三是在问题规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件,(,以规模未到达直接解答大小为条件,),，无条件递归调用将会成为死循环而不能正常结束。,第19页,