高中信息技术选择性必修1第15课迭代与递归教学设计

高中信息技术选择性必修1第15课迭代与递归教学设计本课指向浙教版高中信息技术选择性必修1《数据与数据结构》中“迭代与递归”的核心内容，面向高二或高三完成必修课程学习、已经具备Python基础语法与简单算法经验的学生。教材把它安排在数组、链表、栈、队列、树等结构意识逐渐形成的节点上，意图不是让学生多背两个名词，而是让他们在“重复”这一计算现象面前分辨两种逼近问题的方式：一种用状态持续推进，一种用问题自我缩小。教学立意落在三句话上：会用循环刻画不变量，会用分治刻画自相似，会在效率、可读性、边界与安全之间作出有证据的选择。一、学情研判与内容定位学生已经能写出for与while循环，能完成累加、计数、查找最大值等任务，对函数定义与调用也不陌生；真正困难在于把“同一个问题在更小规模上重演”看成可计算的依据，而不是玄学。常见迷思集中在四处：把递归理解成函数绕圈；忽视终止条件，把边界当成最后补救；说不清递归调用时参数、局部变量与返回值的去向；把递归天然等同于慢，把迭代天然等同于优。选择性必修1的价值恰在于连接程序语言与数据结构，迭代靠近显式状态机和循环不变量，递归靠近数学归纳、树形展开与调用栈。本课应避免上成语法复习课，也不应滑向竞赛技巧展示，而要在常规课堂可达的深度里建立“问题结构决定算法形态”的判断力。课标对计算思维的要求强调抽象、分解、建模、算法设计与评估，本课天然承载这些要素。把“求前n项和”写成循环，是把累计器的不变性说出来；把“阶乘”写成n乘以小一阶的答案，是把归纳假设交给调用机制；把“斐波那契”从朴素递归改到记忆化或迭代，是让学生亲眼看见重复子问题如何吞噬时间；把“汉诺塔”从仪式化口诀还原为三根柱上的状态移动，是训练学生把过程抽象为“移走上层、移动底盘、移回上层”的自相似结构。知识目标、能力目标与价值目标不能分层割裂，课堂每个环节都应同时触摸概念、代码与证据。二、教学目标与评价证据学生完成本课学习后，应能用自然语言、流程图和Python代码三种表征解释迭代与递归的差异；能为给定问题识别最小子问题、基例与递推关系；能画出至多三层递归调用树并说明返回值的汇合顺序；能就阶乘、斐波那契、列表求和、目录遍历、二分查找、汉诺塔六类任务选择合适方案，并用时间复杂度、空间开销、可读性与异常风险支撑选择；能在Python环境中设置合理的递归深度观察RecursionError，进而讨论工程限制不是理论错误的替代品；能在同伴代码中定位缺少基例、基例不可达、子问题没有严格变小、重复计算过密等典型缺陷。评价不依赖课后一张卷，而嵌入三个可观察产物：一张“同一问题双解”的对照表，一段带注释的递归追踪单，一份把坏递归改成稳态迭代的重构记录。三、重点难点与处理策略重点落在递归三要素的精确表述：基例给出无需再分解的答案，递推把原问题交给一个或多个严格更小的同类问题，收敛保证所有路径迟早触达基例。难点不在写对factorial，而在理解调用栈保存现场、返回现场、合并结果的时序；在于区分“能递归描述”与“适递归实现”；在于面对重叠子问题时知道何时引入缓存，何时改写迭代，何时保留递归换取结构清晰。处理策略是“小步子显影”：把不可见栈帧外化为卡片，把返回值流动外化为箭头，把复杂度差异外化为同规模输入下的计数实验，把错误外化为可复现的最小样本。教师少给结论，多制造一次可观察的冲突：当n从10变到30，双分支递归为何突然失速；当列表长度逼近系统限制，优雅递归为何先败给内存。四、教学准备与课堂组织机房一人一机，安装Python3.11及以上版本，准备可离线运行的编辑器与计时工具；学生平板或纸质学习单二选一，避免设备差异抢走思维时间。课前投放三个热身片段：循环求1加到100，函数版求和但内部仍用循环，以及一个故意去掉return的“半成品递归”，让学生带着“函数也可以参与重复吗”的疑问进入。黑板分区固定为左中右：左侧写问题，中央画结构，右侧留证据。小组四人为宜，角色分为驾驶员、领航员、记录员、质询员，每十二分钟轮换一次，保证不只是手快的学生占据键盘。教师准备红牌与绿卡各若干，红牌标记“子问题未缩小”，绿卡标记“基例清晰”，让课堂纠错具备共同暗号。五、情境导入：从排队报数到问题折叠上课伊始，教师请第一列学生玩一个安静报数：末尾同学知道自己要报“前面人数加一”，于是他只问前一位，前一位再问更前一位，直到排头说出“我是一”，随后声音沿原路折返，一个一个加回。学生立刻发现这里没有一个同学掌控全局，却能得到总数；每个人都做了同一件小事：向下追问一次，向上回报一次。教师板书两句话：若前面有n减1人，我报n；若前面没人，我报1。用代码呈现为defcount(k):return1ifk==1elsecount(k1)+1。这里没有循环关键词，重复却真实发生；重复不靠while维持，而靠参数变小维持。这个温度很低的开场把递归从术语拉回身体经验：重复可以展开成圈，也可以折叠成链。随后给同一任务配一个迭代对照：total=0;foriinrange(1,n+1):total+=i。教师不评判高下，只追问：哪一段代码保存“已经加到几”，哪一段代码保存“还差几层没返回”。学生被迫区分显式变量与隐式栈帧，课堂从一开始就避开“递归高级、循环低级”的虚荣比较，转向机制辨识。六、探究一：迭代的本质是可检验的不变量任务一给定整数数组，求偶数平方和。学生先独立写循环版本，要求在注释中写出循环不变量：每次处理完前i个元素后，acc保存其中所有偶数的平方和，i指向下一个待看元素。样本输入为[1,2,3,4]，运行到i等于3时，acc应等于2的平方加4的平方，即20。教师巡视时不看运行结果，先看不变量是否写得出；能写出不变量的学生，循环边界很少出错。接着把任务改为“边读边求和，读到负数停止”，学生自然改用while，并讨论哨兵值、输入合法性与循环条件的先后顺序。此处强调迭代不是for的同义词，而是“状态按规则迁移，直到谓词不再成立”。归纳共同点时，教师只用三问收束：状态是什么，迁移靠什么，停止凭什么。学生答出“状态是累计器与位置，迁移依赖当前元素，停止凭索引越界或哨兵出现”，就抓住了迭代的骨架。此时引入复杂度，一维遍历写作O(n)，额外空间常数写作O(1)，公式以所见即所得方式呈现：T(n)=O(n)，S(n)=O(1)。教师要提醒，O(1)空间不等于没有变量，而指辅助空间不随输入规模显著增长；这句纠偏能挡住后续把递归所有开销都神秘化的倾向。七、探究二：递归的本质是可信的自我引用从报数过渡到阶乘。学生口述数学定义：0!=1，n!=n×(n1)!。教师要求把句中“×”右侧看作同一函数的新任务，代码自然落成deffact(n):return1ifn==0elsenfact(n1)。关键不在能运行，而在追踪fact(4)时如何展开：fact(4)等待fact(3)，fact(3)等待fact(2)，fact(2)等待fact(1)，fact(1)等待fact(0)，fact(0)交出1；随后向上依次返回1、2、6、24。学生在学习单上画五条横线表示栈帧，右侧箭头标出返回值汇入乘法的位置。此环节必须放慢，因为“先一路向下，再一路向上”的对称感，是递归审美也是递归风险。质询环节设置三个陷阱：把基例写成n==1导致fact(0)失控；把递归调用写成fact(n)产生原地打转；遗落return造成None参与乘法。每组拿到一张错误卡，用红牌或绿卡标注病灶，再说出最小复现输入。通过“最小复现”训练，学生理解调试不是把程序看fuzz到正常，而是找到仍暴露错误的最小输入。教师顺势提出递归三可信：子问题类型相同，规模严格更小，基例可达且答案正确；缺一，即不可信。八、对照实验：当斐波那契暴露重叠子问题同一个数列给两种写法。迭代版从a,b=0,1出发，循环n次执行a,b=b,a+b；朴素递归版写成deffib(n):returnnifn<2elsefib(n1)+fib(n2)。输入取10、20、30，学生记录秒表时间与调用次数。递归版在n等于30时尚能忍受，调到35附近课堂出现可感停顿；调用计数呈近似指数膨胀，fib(5)的子树里fib(3)与fib(2)被反复展开。教师在中央黑板画出fib(5)调用树，用不同颜色圈出重复节点，学生直观看到“不是递归慢，而是这棵树的枝叶被同一问题反复占领”。改造分两条路。路径甲加缓存：fromfunctoolsimportlru_cache后保留递归形态，重复子问题只算一次，时间压到O(n)，空间仍与会话深度和缓存规模相关。路径乙改迭代：陆续推出f(0)、f(1)、……、f(n)，只保留最近两项，时间O(n)，额外空间O(1)。学生据此填写对照句：当问题呈现单向依赖且只依赖有限历史，迭代更省；当问题天然树形分解且子问题少重叠，递归表达更贴；当递归暴露重叠子问题，先想记忆化，再想递推化。课堂不把“尾递归优化”讲成Python救命稻草，因为CPython并不保证尾调用消除，工程判断必须基于解释器事实。九、结构引入：树、目录与不可见栈递归真正的舒适区不是数列，而是结构本身具有自相似的对象。教师展示一个项目文件夹树：根目录下有src、docs、tests，src里还有core与utils。任务是统计.py文件数量。学生容易写出os.listdir配合循环，却在子目录里卡住；一旦承认“每个子目录都是一棵更小的目录树”，递归立刻合身：当前目录的答案等于本层命中数加各子目录答案之和。伪代码保持课堂通用：若路径是文件且以.py结尾，返回1；若路径是目录，返回其子项答案之和；空目录返回0。学生用缩进手画三行调用，体会到目录shifting不需要显式栈，因为运行时栈替它保存待回访的分支；若改成迭代，则要自己维护栈或队列。此处完成一次关键反转：有时递归不是消耗栈，而是把本就存在的栈交给语言管理。二分查找提供另一种对照。有序列表中查找目标，递归版每次把区间折半，迭代版用lo与hi维护不变量：目标若在，必在闭区间[lo,hi]内。两版都O(logn)时间，但递归版在极端长度下仍受深度限制，迭代版则更贴近工业代码习惯。学生讨论后形成一句冷静结论：结构自相似鼓励递归表达，性能与边界条件决定最终落地形态。比记住句子和更重要的是，他们能举出反例与正例。十、难点突破：从坏递归到稳态程序的重构工坊工坊材料是一份有病的“列表求和”：defs(a):returna[0]+s(a[1:])，无基例，切片还会复制新列表。学生先做病理切片：空列表会触发IndexError；每个递归层又制造新子列表，时间看似O(n)却叠加切片成本，实际可退化到O(n²)；深度随长度增长，长列表触发RecursionError。重构给出三个等级：入门版先补ifnota:return0，正确但仍有切片；进阶版传索引defs(a,i):return0ifi==len(a)elsea[i]+s(a,i+1)，避免复制但保留栈深；稳态版改迭代acc=0;forxina:acc+=x。教师强调重构不是审美洁癖，而是用证据切除风险：谁复制数据，谁消耗栈，谁让边界变成概率事件。此处插入安全与责任。递归进入文件系统、网络目录或用户输入生成的嵌套结构时，深度可能不可控；符号链接成环还会让目录遍历永不停止。学生需要知道真实系统会加访问计数、深度上限、已访集合与权限判断。把“能跑”与“可负责”分开，是选择性必修阶段应有的信息社会责任教育：算法不是竞赛棚里的一次烟火，而是可能被陌生人输入击打的公共服务。十一、课堂练习的梯度设计练习分四层，全部短而硬。A层要求把递推关系翻译成代码：给定f(0)=1，f(n)=2×f(n1)，求f(n)，写出递归与迭代两版并说明为何它们都表达2的n次幂。B层给缺基例的求长度函数，让其补基例并设计三个测试：空列表、单元素、含嵌套误用预期异常。C层给汉诺塔三盘，要求不背口诀，写出move(n,src,mid,dst)的调用序列并解释为何总步数满足M(n)=2×M(n1)+1且M(1)=1，由此推出M(n)=2ⁿ−1。D层开放：在“表达式括号匹配”“迷宫回放”“组织树汇总”中任选一题，只用文字画出子问题缩小证据，不急着编码。层次之间允许跃迁，但不允许跳过证据；快的学生去做质询员，慢的留住驾驶权，评价看论证而非先后。十二、教学过程详案：九十分钟展开课前五分钟，屏幕只放两句话：重复可以围成圈，重复也可以压成链；学生把预习半成品上交到共享目录。开课八分钟，报数活动与fact骨架建立直觉，教师收集三个问题写在右侧证据栏：谁在保存中间结果，调用会不会回头，n很大会发生什么。中段二十分钟进入迭代不变量与阶乘栈帧，学生两人一组完成追踪单，教师只回答以“你已经在哪一层”的问题，不替画箭头。随后十五分钟斐波那契计时冲突点燃复杂度讨论，同组分别跑朴素递归与缓存递归，把数字写进对照表。再二十分钟转入目录树与二分，完成“结构是否自相似”的分类卡。末段二十分钟做重构工坊，每组把一段坏递归改到可交付，并在全班用一分钟陈述风险来源。课堂最后五分钟不讲新知，学生写出门条：我今天仍不相信的一件事；我明天愿意验证的一段代码；我改掉的一个口头禅。教师收走门条，下节课从其中三张开始。九十分钟内教师的语言需要克制。示范代码不超过十行，超过即失去思维重量；每次总结只提炼一个可迁移句式，如“参数必须走向基例”，或“返回值要有人接住”。对学生的错误不贴人格标签，只指向机制：这不是粗心，而是子问题没有严格变小；这不是不会递归，而是把切片成本看漏了。课堂气氛应像一间编译车间，安静、有节拍、允许返工，反对把递归讲成魔术，也反对把迭代讲成苦力。十三、板书与可视化方案黑板左区常驻一个问题三角形：顶点写原问题，底部写基例，斜边写递推；任何新任务进来，先填满三角再编码。中区画栈帧：函数名、参数、返回地址、局部值四列，最多画五层，超过即改用省略号并说明省略不是跳过证据。右区是证据栏，只写数字与现象：fib(30)调用次数，目录树的深度，RecursionError触发的n，二分迭代与递归的相同比较次数。投影用于跑代码，黑板保留推理，二者不互相替代。课后把右区数字拍照进班级档案，作为下一课“排序与搜索中的分治”开启材料；递归不是孤岛，它会在归并排序、快速排序、树的遍历中反复回来。可视化公式一律保持所见即所得：fact(n)=1当n=0；fact(n)=n×fact(n−1)当n>0。斐波那契写为F(n)=F(n−1)+F(n−2)，F(0)=0，F(1)=1；其朴素递归调用数近似按F(n)增长，故时间呈指数级，记忆化后每个子问题只求一次，时间回到O(n)。汉诺塔写为M(n)=2M(n−1)+1，M(1)=1，展开得M(n)=2ⁿ−1。所有符号直接呈现，不借助脚注，不制造参考文献幻觉。十四、差异化支持与常见误区干预基础薄弱学生先不碰斐波那契双分支，只守住三条单链：报数、阶乘、列表长度；用实体卡片模拟压栈与弹栈，手先于脑建立顺序。学有余力者进入“递归到迭代的系统转换”：显式栈保存帧，模拟局部变量与返回点，比较与函数式语言的尾调用写法差异；但必须提交一句说明：Python解释器不因写法优雅而奖励无限深度。对容易炫耀技巧的学生，加码约束为“不用递归求目录大小，只许用栈；再不用栈求同一任务，只许用递归”，让其在限制中体会结构。对害怕错误的学生，规定每次运行必须先写下预期，再见真实输出，把情绪从结果抽离到假设检验。误区干预要有现成对话。学生说递归更高阶，教师反问：高阶到连n等于一万都不敢运行吗。学生说循环更土，教师展示编译器与系统库代码片段思路，说明工业世界偏爱可预期状态。学生把lru_cache当万能胶，教师让其缓存一个依赖外部随机数或当前时间的函数，观察结果失效；purity不在本课展开，但“可缓存性依赖输入决定输出”必须点到。学生把基例当补丁，教师要求倒着设计：先写最小问题的答案，再让大一点的问题去借它，顺序一换，递归就不像求生欲，而像建筑学。十五、作业设计与课后延伸作业控制在一页。必做一：把阶乘递归改写为迭代，再写循环不变量；把阶乘迭代改写回递归，标注基例与收敛方向；两道小题意在打通双向翻译。必做二：给定一个可能含环的模拟目录字典，写带已访集合的统计函数，解释为什么visited比depth更能防环。必做三：阅读一段陌生递归，不运行，先预测输出，再指出若输入翻倍最可能先撞墙的是时间、栈深还是内存。选做：研究sys.getrecursionlimit与sys.setrecursionlimit，写一段不超过一百字的团队规范，说明何时允许调整上限、调整前必须完成的三项检查。禁止布置“用递归画炫酷分形”作为强制任务，美观不能替代边界安全；愿意探索者可在社团时间继续。延伸连接到后续单元：排序中的归并让学生看见“分治—递归—合并”的完整三角；树遍历让先序、中序、后序从背诵变成访问时机；动态规划从重叠子问题进入状态定义。教师在