(
课件网) 教科版高中信息技术 必修1 数据与计算 第4单元 计算与问题解决 4.3 非数值计算（第2课时） 课堂导入 “汉诺塔”游戏源于一个古老的印度传说。如下图所示，在木板上有A、B、C三根杆，A杆上有若干木盘，规定每次移动一个木盘。且小的木盘只能叠在大的木盘上面。请设计算法，用尽可能少的次数把所有的木盘从A杆全部移到C杆上。 直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。 递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段， 也是一种问题求解的重要方法。 递归 递归函数是只用函数自身来定义该函数的方法。如斐波那契数列“1,1,2,3,5,8,13……”,可以递归定义为 F(n)= 1(n=1或n=2) F(n-1)+F(n-2)(n>2) 递归的基本思想： 递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。 递归可用“分”，“治”，“合”三个字概括： 分：将原有问题分解成K个子问题。 治：对这K个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。 合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解 汉诺塔游戏源代码和运行界面截图： 小 结 1、理解递归思想。 2、理解递归算法。 练 习 结合4.2的知识，计算“汉诺塔”游戏移动的次数。 def f(n): if n==0: return 0 else: return 2 f(n-1)+1 x=int(input("请输入塔的个数：")) print("需要移动",f(x),"次") input("运行完毕，请按回车键退出...") 汉诺塔移动次数源代码和运行界面截图： 拓展知识 迭代程序可以转换成等价的递归程序。以上一节中计算斐波那契数列第N项的值为例，程序间的转换如表所示。 迭代与递妆算法都需要重复执行某些代码，两者既有区另又有密切的联系。迭代是重复反馈过程的活动，其目的通常是逼迫所需目标或结果。递归是重复调用函数自身。递归满足终止条件的情况时逐层返回。迭代则通常使用计数器结束循环。 THANKS
