递归教学设计
课程标准 和 教学目标 递归
教材内容：5.2迭代和递归 之 递归
适应的课程标准： 1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。
教学目标： ●能结合具体程序实例，掌握递归函数的定义。 ●能够运用递归的思想和方法，编程实现“汉诺塔”。 指向的核心素养： ●信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。 ●计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。 ●数字化学习与创新：要使学生熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。 ●信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。
学习环境：有教学控制软件的多媒体机房，python编程环境。
建议课时：1课时
教学活动设计 教学环节 教学过程 设计意图
情境导入 导入1：展示“俄罗斯套娃”，略加简介：相传俄罗斯民族有两家表亲相邻，表兄妹童年相伴长大，后来表兄远走它乡，由于思念家乡的表妹，每年做木娃娃，一年比一年做的娃娃大。数年后，他回到了家乡，将娃娃送给了表妹，后人模仿传称套娃，又叫吉祥娃娃。引入递归的思想。 导入2：分形图案生成（递归算法），选择IDLE中的Help菜单——Turtle Demo——Fractalcurves，简介其基本原理。 通过导入生活中的递归案例，以便顺利过渡到递归算法思想的分析。
学习任务一：阶乘问题 ●学习任务一：阶乘问题 问题：利用递归算法求n的阶乘（n!=1×2×…×n）。由数学知识可知，n阶乘的递归定义为：它等于n乘以n-1的阶乘，即n！=n*(n-1)!,并且规定0的阶乘为1。设函数fac(n)=n!，则fac(n)可表示为： 展示一般递归函数定义方法： 程序测试效果def fac(n): if n == 0: s=1 else: s= n * fac(n-1) return s print(fac(3))6
描述递归过程： 对应地，可以跟踪递归函数中参数n的变化情况： 程序测试效果def fac(n): if n == 0: s=1 else: print(str(n)+'*fac('+str(n-1)+')') s= n * fac(n-1) return s print(fac(3))3*fac(2) 2*fac(1) 1*fac(0) 6
设问： 前面，我们已经学习过斐波那契数列的递推公式： a1 = 1 a2 = 1 an=an-1+an-2(当n>2时) 你能编写对应的递归程序由计算机计算一年后的兔子总数吗？ 参考程序： Fibonacci程序递归算法： def fib(n): if n == 1 or n == 2: return 1 else: return fib(n - 1) + fib(n - 2) print("到12月共有%d只兔子." % (fib(12)))
教师总结：能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。特别地，如当规模N=0或1时，能直接得解。因此，在设计递归算法时，要满足两个条件，即要确定递归公式和递归结束条件。 设计意图：递归是程序设计里面比较高级的技术。递归函数的定义比较特殊，它基于自己定义自己。初学者感觉困惑的地方就在于：这种定义方法有意义吗？这是一种循环定义吗？建议使用简短例子，介绍递归函数的定义方法，递归公式的建立，以及递归结束条件。引用上节已经练习过“兔子有多少只？”程序实例，学生动手写递归程序，初步体会“迭代算法”与“递归算法”的区别。通过对递归程序的执行过程的仔细分析，同时跟踪递归函数中参数的变化，引导加深概念理解，最后总结递归算法的执行过程中的递推和回归两个阶段。
自主学习 学生自主编写程序，教师及时跟踪、辅导、点评、总结 参考程序： Fibonacci程序迭代算法一： rabbit = [0,1,1] for i in range(1,11): x = rabbit[-1] + rabbit[-2] rabbit.append(x) print(rabbit)
Fibonacci程序迭代算法二： a = 1 b = 1 print(a) print(b) for i in range(3,13): c = a + b print(c) a = b b = c
算法一通过数组的形式实现，它与数学中“数列”的关系紧密，便于与数学学科横向联系，算法二设置了三个变量，巧妙地用了a，b，c三个变量来中转兔子的数量，初始时，a,b都为1，从第三个月开始，c表示总数，a表示新生下来的兔子或者前两个月的时候就存在的老兔子，也就是an-2，b表示前一个月底已经存在的兔子，也就是an-1，如此滚动向前计算。体会其中a和b的变化情况。算法二更集中地体现了计算机中迭代算法的特点。 对学生编程中不同的实现方式，即时发现、即时点评，可以让学生互评、自评，激发大家探索与思考。
学习任务二：汉诺塔游戏 ●学习任务二：汉诺塔游戏 汉诺塔游戏更为复杂，为了更好地理解这个问题。教材对此问题进行了详细的分解。一是抽象与建模；二是设计算法；三是编写程序。上一节中课后习题第5题，我们专门设置了对应的习题，学生应该对这个问题有所了解。建议本块内容教学按照学生的思维规律，由具体到抽象，由简单到复杂，依序进行。 1.抽象与建模 为了明确规则，推演过程，选择IDLE中的Help菜单——Turtle Demo——Minimal_Hanoi，使用现成的数字化学习工具，直观展示“迷你汉诺塔”游戏的动画过程。 考虑一般情形，为了将n个盘子从A柱经过B柱移动到C柱，可建立如下模型： (
将n-1个盘子从A柱经过C柱移动到B柱
将A柱中剩下的一个盘子移动到C柱
将n-1个盘子从B柱经过A柱移动到C柱
) 设计意图：递归是计算思维能力之一。首要是寻找和发现问题的规律与内部结构。能够由具体情况概括出一般规律，通过本问题的细致分析，学生可以体会到抽象与建模的基本过程。 2.设计算法 根据上述抽象与建模可以发现，原来与n有关的问题变成了与n-1有关的问题，重复这个过程，每次n减1，最后当n=1时，直接移动该盘子。因此，该问题可采用递归算法来实现，即： （1）定义一个实现盘子移动的函数move。如将n个盘子从A柱经过B柱移动到C柱，可调用函数move(n, a, b, c)，其中，n表示A柱上的盘子个数，a、b、c分别表示A柱、B柱、C柱。 （2）将n-1个盘子从B柱经过A柱移动到C柱，可以分解成如下递归调用： move(n-1, a, c, b) a→c move(n-1, b, a, c) （3）当n=1时，直接移动盘子，递归结束。 设计意图：难点在于根据模型写出对应的程序实现，而本算法中的函数参数是疑难点。实参与形参的区别、参数在每次递归中变化情况，可以略加展开说明。 3. 编写程序 根据算法，得到的程序及测试效果如下： 程序测试效果def move(n, a, b, c): if(n == 1): print(a,"->",c) return move(n-1, a, c, b) move(1, a, b, c) move(n-1, b, a, c) move(3, "A", "B", "C")A -> C A -> B C -> B A -> C B -> A B -> C A -> C
计算思维能力的培养，首要是问题的抽象与建模。它是决定问题解决的关键之一。其次，算法设计是重点与难点。可以在模型指导下配合讲解递归函数的设计，鼓励学生自己动手编写程序。尝试修改函数中的次数参数，观察参数变化带来不同的效果。
拓展学习 递归程序一般具有如下结构： （1）首先指出数据规模“最简单”的情况，数据如何进行计算。 （2）数据规模“较复杂”的情况，可以归结为“较简单”的数据计算。 递归程序的程序正确性与数学归纳法紧密联系。数学归纳法的基本证明过程： （1）验证当n = 1（或其它值）时，递归式成立。 （2）假设当n = k时，递归式成立，证明n = k+1时，递归式亦成立。 具体使用递归时应避免“无限递归”的情形。如果一个递归永远也达不到基准情形，则它会永远继续递归调用，而程序也永不停止。这个现象称为“无限递归”。下面是一个会引起无限递归的最简单的函数： Def recurse(): Recurse() 无限递归的函数并不会真的永远执行，python运行环境会在递归深度达到上限时报告一个出错信息：“RuntimeError:Maximum recursion depth exceeded”，即“运行时错误：超出最大递归深度”（默认上限为1000） 递归设计是一个难点，而它的基本思想原理与数学归纳法密切相关，同时还应当注意“无限递归”问题。
课堂小结 知识梳理： 1. 递归代算法的基本思想与应用； 2. 递归算法的实现技术； 3. 递归算法的数学原理与注意事项。 迭代表达式的建立是难点，课后作业提供了相应练习。
作业布置 基础作业（面向所有学生）： 完成课本“思考与练习”第4题 本节安排了三道题目，也可以结合本章习题布置作业。 课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。
教学设计思路 本课内容为递归，建议分配1课时完成。递归在解决一类问题时十分有用，往往描述简洁，易于理解，并能极大地减少程序代码量。它的关键在于识别出内在的递归结构。 它与高中数学教材中的“数学归纳法”原理紧密相连，了解这个原理更有助于知识内容的理解与掌握。 首先，启发学生对“递归”思想有所感悟，可以引用生活的事例（比如俄罗斯套娃），或者从身边的小事讲起，例如“帮拿作业本”。 其次，以阶乘为例，介绍其递归公式，引入递归函数的定义。然后重点强调设计递归算法时，要满足两个条件：确定递归公式和递归结束的条件。 再次，为进一步引导学生使用递归算法来解决问题，可以使用汉诺塔游戏为例，重点放在问题的分解与综合上，重点在于提示其内在的递归结构。 本节主要内容为递归。学生对于递归相对陌生，理解难度较大，建议从抽象与建模、设计算法、程序实现三个方面，深化细化，引导学生理解并掌握递归算法。
针对 核心素养培养的 设计考虑 信息意识、信息社会责任：本节课在导入时选择了两个案例，导入一“俄罗斯套娃”来自生活，导入二“分形图案生成”，递归算法可以创造出美妙图案；这些实例目的是引起学生探究的兴趣，提示学生意识到递归算法思想的奇妙运用，教师引导总结“即大问题的解决中嵌套着原问题相似的规模较小的问题”，目的是能够启发思考、归纳出递归算法的普遍运用，增强学生对此类问题的敏感性，对递归算法的思想有初步的意识。 计算思维：本节中的递归算法即为计算思维的核心之一，主要表现在如下四个方面：一是如何将一个复杂的问题简单化处理，这体现了简洁性；二是对于每次简化的问题，其表达方式与原方式保持一致，反映了结构性；三是问题解决是有终止的，简化到一定程度，一定是可以解决的，反映了构造性；四是可以用有限的步骤处理近于无限功能的方法，体现了简约性。 数字化学习与创新：本节选择IDLE中的Help菜单——Turtle Demo——Minimal_Hanoi，使用现成的数字化学习工具，直观展示“迷你汉诺塔”游戏的动画过程，为典型的数字工具应用。迭代教学设计
课程标准 和 教学目标 迭代
教材内容：5.2迭代和递归之迭代
适应的课程标准： 1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。
教学目标： ●能结合具体程序实例，掌握迭代的思想和方法。 ●能够运用迭代的思想和方法，编程实现方程根的求解。 指向的核心素养： ●信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。 ●计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。 ●数字化学习与创新：要使学生为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。 ●信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。
学习环境：有教学控制软件的多媒体机房，python编程环境。
建议课时：1课时
教学活动设计 教学环节 教学过程 设计意图
情境导入 导入1：自主编写程序展示“美妙的图案”，引导学生体会python turtle海龟作图的美妙之处，对作图的原理略加简介，引入迭代的思想。 提问：如果将中程序中“t.left(90)”语句的参数90修改为91，效果又如何？ 导入2：“兔子有多少只？”：假定我们有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始怀孕（真实情况是六个月左右），在第二月结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，如此这般持续下去。每只雌兔在开始繁殖后每月都产下一对兔子，假定没有兔子死亡，在一年后总共有多少对兔子？ 请同学们计算前几个月兔子的数量，填写下表，看看能不能找到规律？ 时间（月）1234567……兔子（对）11235
设计意图：通过导入生活中的迭代算法问题，以便顺利过渡到迭代算法思想的分析。
学习任务一：斐波那契数列的求解 ●学习任务一：斐波那契数列的求解 通过同学小组讨论，教师总结“兔子有多少只？”问题的分析过程：若用an表示第n个月底兔子的数目，因为每个月底的兔子可以被分成两个部分：一部分是上个月底就有的兔子an-1,另外一部分就是这个月新生下来的，而这个新生的显然就是上两个月就存在的那些兔子生出来的an-2。 时间1234567……总数112358老兔子111235新兔子001123
我们可以写出这样的递推公式： a1 = 1 a2 = 1 an=an-1+an-2(当n>2时) 设计意图：引入时提供了两个具体实例，特别是第二个需要学生自己动手实践，建议放手让学生讨论并自主实现算法。需要注意的是，学生在编写程序的过程，可能会有不同的实现，应充分尊重学生的想法，放手让学生多想多试。通过“兔子有多少只？”程序实例，学生可以初步理解“迭代算法”的思想实质。通过对实际程序两种实现的对比分析，引导学生自主阅读教材内容，加深概念理解，并由教师引导，总结概括出迭代算法的三个重要方面即“确定迭代变量”、“建立迭代关系式”、“控制迭代过程”。
自主学习 学生自主编写程序，教师及时跟踪、辅导、点评、总结 参考程序： Fibonacci程序迭代算法一： rabbit = [0,1,1] for i in range(1,11): x = rabbit[-1] + rabbit[-2] rabbit.append(x) print(rabbit)
Fibonacci程序迭代算法二： a = 1 b = 1 print(a) print(b) for i in range(3,13): c = a + b print(c) a = b b = c
算法一通过数组的形式实现，它与数学中“数列”的关系紧密，便于与数学学科横向联系，算法二设置了三个变量，巧妙地用了a，b，c三个变量来中转兔子的数量，初始时，a,b都为1，从第三个月开始，c表示总数，a表示新生下来的兔子或者前两个月的时候就存在的老兔子，也就是an-2，b表示前一个月底已经存在的兔子，也就是an-1，如此滚动向前计算。体会其中a和b的变化情况。算法二更集中地体现了计算机中迭代算法的特点。 对学生编程中不同的实现方式，即时发现、即时点评，可以让学生互评、自评，激发大家探索与思考。
学习任务二：牛顿迭代法求解平方根 教材直接提供了牛顿迭代法的算法过程，但里面涉及到几个更细致的问题，可以在时间允许的情况下，采用问题驱动方式，更好地训练学生的计算思维。 问题定义。假设实数已经是一个非常清楚的概念，问题在于什么是平方根？数学上认为，如果x2= y，则非负数x称为y的平方根。这是一个严格的数学定义。但是它并没有给出一种从任一y求出x的方法。从计算的角度来讲，如果平方根是无理数，就不能写成数字的有效表示形式，计算必须在有限的步骤内完成，应该是一个有终止条件的过程。因此一般而言，必须把近似误差e作为参数事先给定。根据我们的分析：你能把我们的问题重新修改一下吗？可以安排小组讨论，共同探究。 数学定义我的定义如果x2= y，则非负数x称为y的平方根。
通过大家共同探究，总结出一个共同认可的操作定义： 对于任意非负实数y，设法找到一个非负实数x，使得，其中e为事先设置的允许误差。 计算思维能力的培养，首要是问题的清晰定义。它是决定问题解决的关键之一，通过本项目问题定义的细致分析，学生可以体会到一个问题的描述性定义与解决一个问题的操作性定义之间的差异。描述性定义指向操作性定义的过程，是思维的一次本质上的飞跃。注意此处的终止条件与教材中的不同，但只要言之成理，思路正确，实现方法可以不同。不必局限于教材的具体实现，建议多启迪学生思维，多元思考。
知识讲解（2） 牛顿迭代法的算法思想如下，你觉得它与操作定义是否一致？是否一定能求出平方根？ 1.设定迭代变量x的初始值x0，如取x0=y/2； 2.确定迭代公式：，并求出x的下一个值xn+1; 3.如此继续下去，直到，迭代结束。 以求2的平方根为例，e取值为10-5，则迭代变量迭代的过程如表所示。 迭代次数xnxn+1111.50.2521.51.4166670.00694431.4166671.4142160.000006
当前后两次求出的为0.000006时，停止迭代，故2的平方根约为1.414216。 首先这个算法描述了一个计算过程，只要能做实数的算术运算、求绝对值、比较大小，就可以机械地重复上述过程。其次这个算法的核心思想是一步步地迭代，从一个初始值逐步地方根，它是一个逼近、近似的过程。这个算法有点必须证明，即该算法在计算x的过程中，序列一定是收敛的，只要迭代的次数足够多，那么就能任意小，因此对任何允许的误差e，这样的迭代都能保证结束。 本例参考代码： 程序测试效果y = int(input("请输入一个需要求其平方根的数：")) x = y / 2 while abs(x * x - y) > 1e-5: x = (x + y / x) / 2 print(y,"的平方根约为",round((x + y / x) / 2,6))请输入一个需要求其平方根的数：2 2 的平方根约为 1.414214
教材参考代码： 程序测试效果a=int(input("请输入一个需要求其平方根的数：")) x=a/2 while ((abs((x+a/x)/2-x))>0.00001): x=(x+a/x)/2 print(a,"的平方根约为",round((x+a/x)/2,6))请输入一个需要求其平方根的数：2 2 的平方根约为 1.414214
试比较二者的细微差别，谈谈你的看法。 用迭代算法处理问题，需要考虑以下三个方面：1.确定迭代变量。2.建立迭代关系式。3.控制迭代过程。牛顿迭代法的程序实现难度不大，建议教师引导学生从多个维度来进行探索：不同的初始值、不同的终止条件对迭代次数的影响。为下一步拓展学习提供思维锚点。
拓展学习 牛顿法的数学原理，在高中数学课本选修2-2第一章“导数及其应用”第2节已经作了介绍，阅读课本相关材料，回答课后两个问题。 设计意图：牛顿迭代法的数学原理是算法的核心与灵魂，离开思想核心，仅关注算法具体实现的细枝末节是舍本逐末。理解它的思想实质，并把它与后面接触的二分查找算法求解方程的根联系起来。埋下伏笔，为后续章节的学习打下基础。
课堂小结 知识梳理： 1. 迭代算法的基本思想与应用； 2. 迭代算法的实现技术； 3. 迭代算法的数学原理与注意事项。 迭代表达式的建立是难点，课后作业提供了相应练习。
作业布置 基础作业（面向所有学生）： 建议完成课本“欧几里德算法”练习 本节安排了五道题目，前三题相对简单，侧重于对变量简单迭代关系的认知，后两题较难，对后续章节的学习也起到了铺垫作用。 课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。建议根据学生的基础和能力，设置不同难度的作业，以满足不同层次的学生需求。
教学设计思路 学生对于三种基本的程序结构已经比较熟悉，顺序结构最简单，实现方便；选择结构需要正确描述条件，只要搞清楚不同情况下如何进行相应处理，用选择语句实现也不太困难；困难的地方，往往是循环结构，由于循环体不仅仅是语句的简单重复，里面还包括变量迭代的技术。 迭代一节，主要问题是求解非负实数平方根的牛顿迭代法，它与高中数学教材数列相关内容紧密相连，了解这个公式的背景，更有助于知识内容的理解与掌握。 首先，启发学生对“迭代”思想有所感悟，可以引用教材中“软件迭代开发”的事例，或者从身边的小事讲起，例如电子钱包、一卡通余额等每日变化情况。或者举例个人的成长经历等，处处都体现了迭代的过程。 其次，可以举一些比较熟悉甚至司空见惯的程序实例，帮助学生理解迭代的思想方法。可以从最简单的话题开始，如变量的重新赋值、更新变量等，逐步过渡到循环语句中的迭代语句。在对“迭代”方法有一定认识的基础上，可以适时与数学中所讲的迭代方法进行类比，以引入牛顿迭代法的思想。 再次，计算平方根的牛顿方法就是迭代思想的巧妙运用。这是本节的难点，主要思想是从一个近似值开始，迭代地优化计算结果，达到问题的求解。教师可以结合牛顿迭代公式的讲解，以程序实例演示：更多的迭代次数，会得到更近似的结果。 本节主要内容为迭代思想与方法，是对学生平常编程经验的总结与升华。应当避免抽象的概念讲解，充分利用学生既有的编程经验，在学生熟悉的程序实例上进行总结、概括，抽取出迭代的思想与方法，进而提炼出迭代算法的三个关键步骤。通过牛顿法求解平方根的问题与讨论，引导学生逐步理解并掌握迭代的一般编程方法。
针对 核心素养培养的 设计考虑 信息意识、信息社会责任：本条目通过设置真实问题情境，简单易懂的程序实例入手，唤起学生对常见编程技术共性的初步体悟，对迭代算法的应用普遍性建立基本的信息意识。本节课在导入时选择了两个案例，第一个案例生动有趣，海龟作图里面角度略微改变（90度修改为91），可以创造出美妙图案；第二个案例“兔子知多少？”，在前面的学习过程中，学生可能早已经接触到该类问题，教师引导总结提升到理论层次的方式，目的是能够启发思考、归纳出迭代算法的普遍运用，对科技发展、工程应用的重要意义。 计算思维：周以真教授认为计算思维是“把一个看来困难的问题重新阐释成一个我们知道问题怎样解决的方法”。导入环节通过简单实例，引入了迭代思想和方法。在教学重点、难点的把握上，特别是牛顿迭代法求根的问题中，教学中专门设计了“问题定义”环节，把一个“平方根”的数学定义转化成了一个可计算的操作定义，为引入牛顿迭代法作好很好的铺垫；牛顿迭代法求根算法，是迭代思想与方法的深化；拓展提高阶段，引入数学材料，引导学生深入到牛顿算法的数学原理，对算法的注意事项能够有更深的理解。 数字化学习与创新：本节在导入一中，通过编写的图形界面小程序——美妙图案的生成过程，展示了迭代算法的魅力，为典型的数字工具应用。
