递归算法与递归程序.ppt

递归算法与递归程序;导入:大家玩汉诺塔游戏：?这个游戏盘子在A、B、C三根柱子上不停运动，有没有规律，和你在照过镜子时遇到的情况相同吗？;当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果甲、乙两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”!为什么会有这么奇妙的现象呢?原来，甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，而且这样反反复复，就会产生一连串的“像中像”。这是一种递归现象。;递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解;问题4-16：著名的意大利数学家斐波那契(Fibonacci)在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子??(当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖);我们不难用以前学过的知识设计出如下算法：;参考程序如下：;开动脑筋：我们有没有更简单的方法解决该问题呢？;(1)分析问题。;仔细研究表4-8，你有些什么发现？每一个月份的大兔数、小兔数与上一个月的数字有什么联系，能肯定这个规律吗？恭喜你，你快成功了？;(2)设计算法。;前面学过：;(3)编写程序。;(4)调试程序;4.5.2??一个应用递归算法解决的问题经典例子;问题4-17：传说在古代印度的贝拿勒斯神庙，有一块黄铜板上插了3根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着64个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面3条规则：

第一，一次只能移动一个金盘。

第二，每个金盘只能由一根宝石柱移到另外一根宝石柱。

第三，任何时候都不能把大的金盘放在小的金盘上。

神话说，如果僧人把64个金盘完全地从一根宝石移到了另外一根上，世界的末日就要到了。当然，神话只能当故事来听，世界不可以因为个别??的活动而导致末日。不过，从僧人搬完64个金盘所需时间的角度来说，即使僧人每秒都能移动一个金盘，那也得要几千亿年！;(1)分析问题。;(2)设计算法。;前面已经学过：;(3)编写程序（引导学生编写程序）;(4)测试程序;?小结：;递归算法的特点;递归算法的实质;递归算法解决问题的特点：;递归算法所体现的“重复”一般有三个要求：