1、递归教学设计课程标准和教学目标递归教材内容：5.2迭代和递归之递归适应的课程标准： 1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。教学目标： 能结合具体程序实例，掌握递归函数的定义。能够运用递归的思想和方法，编程实现“汉诺塔”。指向的核心素养： 信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题
2、进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。数字化学习与创新：要使学生熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。学习环境：有教学控制软件的多媒体机房，python编程环境。建议课时：1课时教学活动设计教学环节教学过程设计意图情境导入导入1：展示“俄罗斯套娃”，略加简介：相传俄罗斯民族有两家表亲相邻，表兄妹童年相伴长大，后来表兄远走它乡，由于思念家乡的表妹，每
3、年做木娃娃，一年比一年做的娃娃大。数年后，他回到了家乡，将娃娃送给了表妹，后人模仿传称套娃，又叫吉祥娃娃。引入递归的思想。导入2：分形图案生成（递归算法），选择IDLE中的Help菜单Turtle DemoFractalcurves，简介其基本原理。通过导入生活中的递归案例，以便顺利过渡到递归算法思想的分析。学习任务一：阶乘问题学习任务一：阶乘问题问题：利用递归算法求n的阶乘（n!=12n）。由数学知识可知，n阶乘的递归定义为：它等于n乘以n-1的阶乘，即n！=n*(n-1)!,并且规定0的阶乘为1。设函数fac(n)=n!，则fac(n)可表示为：展示一般递归函数定义方法：程序测试效果def
4、 fac(n): if n = 0: s=1 else: s= n * fac(n-1) return sprint(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 sprint(fac(3)3*fac(2)2*fac(1)1*fac(0)6设问：前面，我们已经学习过斐波那契数列的递推公式：a1 = 1a2 = 1an=an-1+an-2(当n2时)你能编写对应的递归程序由计算机计算一年后的
5、兔子总数吗？参考程序：Fibonacci程序递归算法： def fib(n):if n = 1 or n = 2:return 1else:return fib(n - 1) + fib(n - 2)print(到12月共有%d只兔子. % (fib(12)教师总结：能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。特别地，如当规模N=0或1时，能直接得解。因此，在设计递归算法时，要满足两个条件，即要确定递归公式和递归结束条件。设计意图：递归是程序设计里面比较
6、高级的技术。递归函数的定义比较特殊，它基于自己定义自己。初学者感觉困惑的地方就在于：这种定义方法有意义吗？这是一种循环定义吗？建议使用简短例子，介绍递归函数的定义方法，递归公式的建立，以及递归结束条件。引用上节已经练习过“兔子有多少只？”程序实例，学生动手写递归程序，初步体会“迭代算法”与“递归算法”的区别。通过对递归程序的执行过程的仔细分析，同时跟踪递归函数中参数的变化，引导加深概念理解，最后总结递归算法的执行过程中的递推和回归两个阶段。自主学习学生自主编写程序，教师及时跟踪、辅导、点评、总结参考程序：Fibonacci程序迭代算法一： rabbit = 0,1,1for i in rang
7、e(1,11): x = rabbit-1 + rabbit-2 rabbit.append(x)print(rabbit)Fibonacci程序迭代算法二： a = 1b = 1print(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表示前一个月底
8、已经存在的兔子，也就是an-1，如此滚动向前计算。体会其中a和b的变化情况。算法二更集中地体现了计算机中迭代算法的特点。对学生编程中不同的实现方式，即时发现、即时点评，可以让学生互评、自评，激发大家探索与思考。学习任务二：汉诺塔游戏学习任务二：汉诺塔游戏汉诺塔游戏更为复杂，为了更好地理解这个问题。教材对此问题进行了详细的分解。一是抽象与建模；二是设计算法；三是编写程序。上一节中课后习题第5题，我们专门设置了对应的习题，学生应该对这个问题有所了解。建议本块内容教学按照学生的思维规律，由具体到抽象，由简单到复杂，依序进行。1.抽象与建模为了明确规则，推演过程，选择IDLE中的Help菜单Turtl
9、e DemoMinimal_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时，直接移动该盘子。因此，该问题可采
10、用递归算法来实现，即：（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)acmove(n-1, b, a, c)（3）当n=1时，直接移动盘子，递归结束。设计意图：难点在于根据模型写出对应的程序实现，而本算法中的函数参数是疑难点。实参与形参的区别、参数在每次递归中变化情况，可以略加展开说明。3. 编写程序根据算法，得到的程序及测试效果如下：程序测试效果
11、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 - CA - BC - BA - CB - AB - CA - C计算思维能力的培养，首要是问题的抽象与建模。它是决定问题解决的关键之一。其次，算法设计是重点与难点。可以在模型指导下配合讲解递归函数的设计，鼓励学生自己动手编写程序。尝试修改函数中的次数参数，观察参数变化带来不同的效果。拓展学习递归程序一般具有如下结构：（1）首先指出数据规模“最简
12、单”的情况，数据如何进行计算。（2）数据规模“较复杂”的情况，可以归结为“较简单”的数据计算。递归程序的程序正确性与数学归纳法紧密联系。数学归纳法的基本证明过程：（1）验证当n = 1（或其它值）时，递归式成立。（2）假设当n = k时，递归式成立，证明n = k+1时，递归式亦成立。具体使用递归时应避免“无限递归”的情形。如果一个递归永远也达不到基准情形，则它会永远继续递归调用，而程序也永不停止。这个现象称为“无限递归”。下面是一个会引起无限递归的最简单的函数：Def recurse(): Recurse()无限递归的函数并不会真的永远执行，python运行环境会在递归深度达到上限时报告一个
13、出错信息：“RuntimeError:Maximum recursion depth exceeded”，即“运行时错误：超出最大递归深度”（默认上限为1000）递归设计是一个难点，而它的基本思想原理与数学归纳法密切相关，同时还应当注意“无限递归”问题。课堂小结知识梳理：1. 递归代算法的基本思想与应用；2. 递归算法的实现技术； 3. 递归算法的数学原理与注意事项。迭代表达式的建立是难点，课后作业提供了相应练习。作业布置基础作业（面向所有学生）：完成课本“思考与练习”第4题本节安排了三道题目，也可以结合本章习题布置作业。课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。教学设计思路本课
14、内容为递归，建议分配1课时完成。递归在解决一类问题时十分有用，往往描述简洁，易于理解，并能极大地减少程序代码量。它的关键在于识别出内在的递归结构。它与高中数学教材中的“数学归纳法”原理紧密相连，了解这个原理更有助于知识内容的理解与掌握。首先，启发学生对“递归”思想有所感悟，可以引用生活的事例（比如俄罗斯套娃），或者从身边的小事讲起，例如“帮拿作业本”。其次，以阶乘为例，介绍其递归公式，引入递归函数的定义。然后重点强调设计递归算法时，要满足两个条件：确定递归公式和递归结束的条件。再次，为进一步引导学生使用递归算法来解决问题，可以使用汉诺塔游戏为例，重点放在问题的分解与综合上，重点在于提示其内在的
15、递归结构。本节主要内容为递归。学生对于递归相对陌生，理解难度较大，建议从抽象与建模、设计算法、程序实现三个方面，深化细化，引导学生理解并掌握递归算法。针对核心素养培养的设计考虑信息意识、信息社会责任：本节课在导入时选择了两个案例，导入一“俄罗斯套娃”来自生活，导入二“分形图案生成”，递归算法可以创造出美妙图案；这些实例目的是引起学生探究的兴趣，提示学生意识到递归算法思想的奇妙运用，教师引导总结“即大问题的解决中嵌套着原问题相似的规模较小的问题”，目的是能够启发思考、归纳出递归算法的普遍运用，增强学生对此类问题的敏感性，对递归算法的思想有初步的意识。计算思维：本节中的递归算法即为计算思维的核心之一，主要表现在如下四个方面：一是如何将一个复杂的问题简单化处理，这体现了简洁性；二是对于每次简化的问题，其表达方式与原方式保持一致，反映了结构性；三是问题解决是有终止的，简化到一定程度，一定是可以解决的，反映了构造性；四是可以用有限的步骤处理近于无限功能的方法，体现了简约性。数字化学习与创新：本节选择IDLE中的Help菜单Turtle DemoMinimal_Hanoi，使用现成的数字化学习工具，直观展示“迷你汉诺塔”游戏的动画过程，为典型的数字工具应用。
