递归算法和递归程序doc资料.ppt

《递归算法和递归程序doc资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归算法和递归程序当你站在甲、乙两面相互面对面的镜子中间时，你会发现什么奇妙的现象吗？你会发现甲镜子里有乙镜子的像，乙镜子里有甲镜子的像，而且反反复复，就会产生一连串的“像中像”。照镜子问题蕴含了递归思想递归法包括2种情况：函数自己调用自己两个函数之间相互调用递归算法：就是一种函数直接或者间接地调用自身的算法。4.5.1从斐波那契的兔子问题看递归算法一、斐波那契的兔子问题1．斐波那契的兔子问题——取自意大利数学家斐波那契的《算盘书》（1202年）(L.Fibonacci,1170-1250）问题假定小兔子一个月就可以长成大兔子，而大兔子每个月就会生出一对小兔子。如果年初养了一对

2、小兔子，问到年底时将有多少对兔子？（假设兔子没有死亡而且严格按照上述规律长大与繁殖）分析1月1对分析1月1对2月1对分析1月1对2月1对3月2对分析1月1对2月1对3月2对4月3对分析1月1对2月1对3月2对4月3对5月5对分析1月1对2月1对3月2对4月3对5月5对6月8对兔子问题分析表1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合计1123581321345589144你会发现时间越长，用列表法解决会很困难。我们需要研究表中的规律，找出一般的方法去解决这个问题。仔细观察表内的数据你会发现第N个月

3、的兔子总数是第N-1个月和第N-2个月兔子总数之和。设计算法假设第N个月的兔子数目是F（N），我们可以得到这样一个递推式：F（N）=F（N-1）+F（N-2）当N>=3F（1）=F（2）=1编写程序同学们自己设计下面的窗体并写出递归程序：调试程序运行程序，在文本框Text1.text中输入月数，得出运行结果。单击此按钮运行程序递归算法基本思想:把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定的程度直到可以直接得出它的解，从而得到原来问题的解。注意：必须要有一个结束递归的条件，不得无限递归。递归法的归纳1：递归算法的实质

4、：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序递归法的归纳2：递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半)；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而

5、每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢