高中信息技术选择性必修1数据与数据结构迭代与递归教学设计

高中信息技术选择性必修1数据与数据结构迭代与递归教学设计一、教材分析本课选自浙教版2019版高中信息技术选择性必修1《数据与数据结构》第五章第二节。本章围绕"算法与数据结构的关系"展开，迭代与递归作为两种基本的算法构造思想，是学生从"会写程序"走向"会设计算法"的关键一步。前一节学生已经掌握了数组、链表等基本数据结构的存储与操作，本节则引导他们发现：同一种问题的求解，既可以用迭代的方式逐步推进，也可以用递归的方式自我分解，而不同的求解方式对时间与空间资源的消耗截然不同。教材以阶乘、斐波那契数列、汉诺塔三个经典案例为主线，先以迭代视角呈现循环结构的普适性，再引出递归的定义、递归三要素（递归调用、递归基例、状态收敛），并通过对比实验揭示递归在空间开销上的代价。这部分内容既是算法思想的升华，又为后续排序、查找分治策略的学习埋下伏笔，具有承上启下的地位。二、学情分析授课对象为高二年级选择信息技术作为选考科目的学生。他们已完成必修1的学习，能够熟练使用Python编写循环、分支和函数，对for循环、while循环的执行过程有扎实的感性认识。但多数学生对"程序调用自身"这一概念缺乏认知基础，容易将递归理解为"死循环"；部分学生能背出递归的定义，却无法独立把现实问题转化为递推关系。教学实践中还发现两个普遍的困难：一是学生难以追踪递归调用时栈的变化，对"递"与"归"的执行顺序模糊不清；二是学生容易高估递归的优雅性而低估其开销，分不清什么时候该迭代、什么时候该递归。因此本课设计的关键，是通过可视化手段把栈的行为还原出来，并安排真实的性能对比实验，让学生在数据面前自然形成判断。三、教学目标1．理解迭代与递归的基本含义，能用自己的语言描述二者的执行过程，判断给定算法属于哪种求解方式。2．掌握递归算法的三要素，能为阶乘、斐波那契数列等问题分别编写迭代版与递归版Python程序，并能画出递归调用的压栈与出栈过程。3．通过运行时间的实测对比，分析递归的开销来源，初步建立时间复杂度与空间开销的量化意识。4．在汉诺塔探究活动中体会"大问题化解为小问题"的分治思想，感受递归在表达复杂问题上的简洁之美，形成严谨、实证的计算思维品质。同时落实课程标准中"通过实例掌握迭代与递归思想，能够分析算法效率"的要求，发展学生的计算思维、数字化学习与创新能力。四、教学重点与难点重点：迭代与递归的思想内涵及递归三要素；同一问题两种算法的程序实现。难点：递归执行过程的可视化理解；递归基例的设计与调用栈溢出问题的分析。突破策略：借助纸牌模拟、实体圆盘操作和逐步插入print语句的方式，把抽象的栈变成可看、可摸、可验证的对象；安排"故意出错"的教学环节，让学生在栈溢出报错中反推递归三要素的必要性。五、教学准备机房环境预装Python3.8以上版本及matplotlib绘图库，每生一台，两两结对。教师准备汉诺塔实物模型一套（供小组传阅操作）、递归调用过程动画、课堂学案（含实验记录表）、在线评测任务单。六、教学过程（一）情境导入：一段会"自己数自己"的音乐（5分钟）上课伊始，教师播放一小段口播音频："在深山里有座庙，庙里有个老和尚在讲故事，讲的什么故事呢？从前有座山，山里有个庙……"笑声中教师提问：这个故事为什么讲不完？它和程序里的死循环一样吗？学生讨论后得出结论：故事在描述自身的过程中引用了自身，但每次描述都完全相同、没有终点，所以它真的停不下来。教师顺势呈现两张图片——一排多米诺骨牌和一面镜子对着一面镜子，引出今天的两个问题：我们能不能让"自己调用自己"这件事有秩序地发生并且停下来？"一步一步往前推"和"层层分解再回归"这两种思路，哪一种更适合计算机？设计意图：用生活化的语言游戏触发认知冲突，让学生在直观的"无限"体验中迫切想知道"怎么停下来"，为递归基例的引入做好心理铺垫。（二）温故探新：用迭代计算阶乘（8分钟）教师提出任务一：计算5!，即5×4×3×2×1。学生几乎不假思索地写出循环代码。教师请一名学生板演并讲解：result=1foriinrange(1,6):result=resulti教师在黑板上以表格形式追踪变量的演化：i从1到5，result依次为1、2、6、24、120。随后教师点拨：这种"以当前结果为起点，按同一规则重复推进，直到目标达成"的求解方式，就是迭代。迭代的核心是循环变量和更新规则，它像爬楼梯，每踩一级，都清清楚楚地知道自己站在哪里。接着教师抛出新问题：能不能换一个角度——不求5×4×3×2×1，而是说"5的阶乘就是5乘以4的阶乘"？学生回应："那4的阶乘呢？""是4乘以3的阶乘。"师生一问一答推进到"1的阶乘是1"，教室里自然安静下来——一个不再依赖更小阶乘的答案出现了。设计意图：以学生最熟悉的计算任务为载体，把迭代概念从"会写"提升为"会说"，同时用连环追问的方式让学生自己推演出递归的表达雏形，使新知从旧知的土壤中生长出来。（三）概念建构：递归的三要素（10分钟）教师展示两段代码的对比，一段是上文的迭代版，另一段是：deffact(n):ifn==1:return1returnnfact(n1)教师指出：函数fact在自己的内部调用了自己。这种函数直接或间接调用自身的求解方式称为递归。请学生对照刚才的问答案对话，找出这段代码与自己的口头推演之间的对应关系。师生共同归纳递归算法的三要素：第一，递归基例，即不需要再分解就能直接给出答案的情形，如fact(1)=1，它是递归的"刹车"；第二，分解规则，把规模为n的问题转化为规模更小的同类问题，如n×fact(n−1)；第三，每次调用必须让问题的规模不断减小，否则永远无法到达基例。为了让学生真正"看见"递归的执行，教师引入可视化环节。在大屏幕上逐帧演示计算fact(4)的过程：main调用fact(4)，fact(4)暂停，等待fact(3)；fact(3)等待fact(2)；fact(2)等待fact(1)；fact(1)返回1；随后逐层回到fact(2)得2、fact(3)得6、fact(4)得24。教师强调：每发生一次函数调用，系统就在调用栈中压入一帧，保存当前函数的现场；函数返回时出栈，恢复上一层现场。"递"是把栈层层垒高的过程，"归"是把栈逐层拆掉的过程。随后进行小组活动：每组发放一叠纸牌，牌面分别写fact(4)、fact(3)、fact(2)、fact(1)，学生模拟压栈出栈，边操作边口头播报每一步的返回值，从而在身体上形成递归执行的肌肉记忆。设计意图：递归的理解必须经历"语言—代码—过程图像"三重表征。纸牌模拟用实物对应抽象的栈帧，把整节课最难的环节拆解成可观察、可复述的动作序列。（四）错例诊疗：递归为什么会停不下来（7分钟）教师故意给出一段有问题的代码：deffact(n):returnnfact(n1)提问：这样写行不行？学生有的说不行，有的说可能行。教师不评判，直接运行，屏幕给出"RecursionError:maximumrecursiondepthexceeded"。教师引导学生读报错信息：解释器对递归深度设置了上限，防止栈空间被无限占用。接着追问：错误证明了什么？学生总结：没有递归基例，规模无限减小也到不了终点；基例是递归的生命线。教师再追问第二个变体：把fact(n−1)写成fact(n)，会怎样？学生迅速反应：规模不变，同样永不终止。由此，三要素的必要性全部被学生以"看到后果"的方式确认。设计意图：让错误在课堂上真实发生，比教师的正确示范更有说服力。报错信息成为教学的证据链，学生由此自然建立"基例—收敛—终止"的因果判断。（五）实测对比：迭代与递归谁更快谁更省（10分钟）任务二：分别用迭代法与递归法计算斐波那契数列第n项，并使用time.perf_counter()测量时间消耗，填入实验记录表：n取10、20、30、35时两种方法分别耗时多少。学生结对编程，迭代版先上架：deffib_loop(n):a,b=1,1for_inrange(n2):a,b=b,a+breturnbdeffib_rec(n):ifn<=2:return1returnfib_rec(n1)+fib_rec(n2)实验数据逐渐浮出水面：n为10时两者都几乎瞬间完成；n为30时，迭代版不足万分之一秒，递归版约需零点几秒；n为35时，递归版开始出现明显等待，个别机房机器上到秒级。教室内响起小声的惊呼。教师追问：计算次数差在哪里？请学生画出fib_rec(5)的调用树——15个结点跃然纸上。学生发现fib_rec(3)被算了3次，fib_rec(2)被算了4次。教师总结：朴素递归按指数级放大重复计算，时间接近O(2^n)，而迭代只是线性扫描，为O(n)；同时，递归的每一层调用都占用栈帧，是实实在在的空间开销。接下来教师点拨一句：能否用列表把已算过的结果记下来？这便是下节课动态规划的萌芽。设计意图：让数字自己说话。学生在亲眼看见递归"变慢"后，对算法效率形成感性而深刻的理解，同时调用树的绘制为理解重复计算提供了直接证据。（六）分组探究：用递归降伏汉诺塔（13分钟）教师提出挑战任务三：有三根柱子A、B、C，A上套着n个大小不同的圆盘，大盘在下小盘在上，每次只能移动一个盘且小盘不能压在大盘之下，如何把所有的盘移到C柱？每组发放三摞大小不一的圆片，学生在A、B、C三个位置上进行实体操作。教师提示：先别管n，先从1个盘、2个盘、3个盘入手，把每次移动的过程写清楚。几分钟后，有小组报告：移3个盘时，我先把上面2个移到B，把最大的移到C，再把那2个从B移到C。教师追问：那你"移2个盘"是怎么移的？学生一愣，随即笑了：跟移3个盘是同一套办法，只是盘子少一个。教师抓住这一瞬间板书：move(n,A,B,C)等价于三步——move(n−1,A,C,B)，把第n个盘从A移到C，move(n−1,B,A,C)。当一个盘时直接移动，这就是基例。请学生独立尝试把这份语言翻译成代码：defhanoi(n,a,b,c):ifn==1:print(a,"→",c)returnhanoi(n1,a,c,b)print(a,"→",c)hanoi(n1,b,a,c)运行hanoi(3)输出七步，学生每一步都在实物上核对，答案与公司操作的完全一致，教室里充满成就感。教师顺势布置思考题：n个盘子最少移动多少次？学生通过n=1、2、3移动次数1、3、7的观察，猜出2的n次方减1，教师讲解递推式M(n)=2M(n−1)+1的推导。教师最后点评递归的价值：斐波那契的递归慢，说明递归并非应有尽有；但汉诺塔用迭代写极其繁琐，用递归只有三行。这说明什么时候用递归不看"漂不漂亮"，而看问题本身是否天然具有自相似的分治结构。设计意图：汉诺塔是培养递归思维最经典的载体。实物操作保障了所有学生的起点，语言到代码的翻译过程让三要素反复被调用，移动次数的猜想又自然延伸到数理归纳。（七）归纳总结与分层作业（2分钟）师生共同梳理本课知识框架：迭代是以循环为基础、通过状态更新逐步逼近目标的求解方式；递归是通过函数调用自身、把大问题分解为同质小问题再逐层回归的求解方式；递归合法的关键是基例与规模收敛；递归用空间换取表达的简洁，迭代更高效但某些问题难以表达，选择依据是问题结构、效率需求与可读性的综合权衡。课后作业分三个层次：基础性作业要求为阶乘、斐波那契写出两种版本并附调用时序图；提升性作业用递归求出一个列表中所有元素之和，并压栈绘图验证；拓展性作业选做楼梯问题——一次走1级或2级台阶，求上10级台阶的方案总数，思考它与斐波那契数列的联系。七、板书设计主板书呈现两幅对照图：左侧"迭代"——初始状态经反复更新走向结果，标注心情词"稳稳地往前走"；右侧"递归"——从大问题逐层拆小到基例再逐层带回，标注心情词"先下去，再上来"。副板书为两个程序的完整代码与fact(4)的栈变化过程，以及斐波那契的实测时间数字。八、教学反思本课最值得肯定的做法，是让递归的理解落在三件具体的事情上：纸牌模拟栈、报错引出三要素、实测数据对比效率。学生的认知不是在听讲中