4.5.1从裴波那契的兔子问题看递归算法

4.5递归算法与递归程序,授课教师：周杰,学习目标了解递归算法的基本概念及执行过程能认识用递归解决问题的方法,递归算法与递归程序,活动一:猴子吃桃问题求解,有一天小猴子摘了若干个桃子，当即吃了一半还觉得不过瘾，又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个。以后小猴子都是吃尚存桃子的一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子在第7天时还剩下多少个桃子?在第1天时共摘下了多少个桃子?,活动一:猴子吃桃算法分析,分析,tao(8)=,(tao(10)+1)*2,tao(9)=,tao(10)=,10,设天数为n桃子数为tao,1,4,(tao(9)+1)*2,tao(n)=,?,(tao(?)+1)*2,1,数学递推公式,活动一:猴子吃桃算法分析,数学递推公式,1,B.顺序执行,A.自己调用自己,函数递归调用,Function如果n=10，则tao=1否则tao=(+1)*2EndFunction,tao(n),tao(n+1),思考：递归算法描述的特点是什么？,递归算法的概念,Functiontao(n)AsIntegerifn=10thentao=1Elsetao=(tao(n+1)+1)*2EndifEndFunction,递归算法执行过程,Functiontao(n)AsIntegerIfn=10thentao=1Elsetao=(tao(n+1)+1)*2,n=1tao(1)=?,tao(1)=(tao(2)+1)*2,Functiontao(2)AsIntegerIfn=10thentao=1Elsetao=(tao(n+1)+1)*2,n=2tao(2)=?,tao(2)=(tao(3)+1)*2,n=3tao(3)=?,Functiontao(3)AsIntegerIfn=10thentao=1Elsetao=(tao(n+1)+1)*2,Functiontao(10)AsIntegerIfn=10thentao=1Elsetao=(tao(n+1)+1)*2,n=10tao(10)=1,tao(3)=(tao(4)+1)*2,?,?,?,tao(4)=190,tao(9)=4,tao(3)=382,tao(2)=766,tao(1)=1534,Functiontao(n)ifn=10thentao=1Elsetao=(tao(n+1)+1)*2EndifEndFunction,递归算法:在程序的函数定义中直接使用或者间接使用的自己调用自己的编程方法。,思考：递归算法的描述特点是什么？,函数名,函数名,递归算法的概念,B.顺序执行,A.自己调用自己,函数递归调用,Functiontao(n)ifn=10thentao=1Elsetao=(tao(n+1)+1)*2EndifEndFunction,递归算法的概念,函数递归调用,活动二：计算机怎样执行递归程序？,递推,回归,递归,活动二：想一想，议一议,输入的第一组数据（3，10）求的是什么?,问题2,第3天的桃子数,382个。,递推与回归的转折点是n=10，tao(10)=1。,问题1,问题3,输入第三组数据，程序运行出现什么结果？请分析原因。,报溢出错误。,问题3,问题1,问题2,输入（1，0）程序不能停止调用递归程序,必须要有结束递归调用的条件,活动二：想一想，议一议,其中“递推过程”有何特点？,C.没完没了,A.小题大做,B.大事化了,问题2,按同一函数模型转化问题到更接近于结束递归的条件。,问题3,问题1,必须要有结束递归调用的条件,活动二：想一想，议一议,按同一模型转化问题到更接近于结束递归调用的条件。,问题1,问题2,问题3,用递归法解决问题的两个条件,必须要有