高中信息技术粤教版选修1递归算法与递归程序教案

高中信息技术粤教版选修1递归算法与递归程序教案本课面向高中信息技术选修模块，对应粤教版选修1中“算法与程序设计”的深化单元，主题为递归算法与递归程序。授课对象已完成Python基础语法、函数定义、条件分支、循环结构和列表操作的学习，能够理解程序执行顺序与参数传递，但对“函数调用自身”的执行图景普遍缺少稳定表象。课堂定位不是再增加一个语法点，而是把递归作为一种可观察、可推演、可迁移的问题解决方式，让维中看见规模缩小的方向，在调用与返回的链条中辨认程序状态，在错误样例的解剖中建立边界意识。核心概念锁定为基准情形、递归情形、规模收敛、调用栈、返回值合成；关键能力锁定为把重复结构改写成自相似定义、为递归函数画出调用树、用打印缩进和断言追踪执行过程、比较递归与迭代的时空代价。课程价值落在计算思维的深处：当学生能把一个复杂问题写成“最小情况可直接回答，一般情况可化归到更小同类问题”的陈述，程序就不再是逐行执行的命令堆，而成为对问题结构的说明。一、教学内容的结构性理解递归在教材中位于函数之后、分治与回溯之前，既得承担“高阶过程抽象”的启蒙，又得为后续树、图、查找、排序中的自相似结构埋下接口。本节不宜被窄化为阶乘、斐波那契、汉诺塔三件套的记忆训练，也不宜拔高为大信息学竞赛式证明课。它的教学重心应放在同一件事反复发生：把n的问题交到n减1手里，把整层目录交到子目录手里，把棋盘的一段交到更短一段手里。学生真正需要跨过的是三道门槛：第一，相信尚未算完的函数可以被再次调用，因为调用不是复制文本，而是建立新的活动记录；第二，承认答案常常不是在前进途中立刻出现，而是在返回到上一层时被拼装出来；第三，发现边界不是附属注释，而是递归合法性的起搏器。基于此，本课选择“阶乘—目录大小—汉诺塔—分形树”作四阶材料：阶乘突出定义直译，目录大小突出真实系统遍历，汉诺塔突出策略表达，分形树突出可视生成与审美创造。四者难度递增，但都围绕同一递归骨架。二、学情诊断与起点证据课前用三分钟采集诊断数据，题目避开机械求值，直接暴露思维方式。第一题给出函数f(n)在n等于0时返回1，否则返回n乘f(n减1)，让学生口答f(4)并说明答案出现的位置；第二题给出残缺函数sumList(a)，基准分支已写出，要求补一行使列表求和成立；第三题给出一个没有终止条件的countdown(n)，询问运行现象与可能后果；第四题为观念题，用“能或不能”判断：一个函数体内出现自己的名字就是死循环。预期中，多数学生能算出f(4)等于24，却说清“24在返回途中逐层乘出”者不足三分之一；补全列表求和时，相当数量学生会写成a加sumList(a)，暴露出把首元素与剩余切片混淆；对无终止倒计时，许多学生能预感报错，却说不清为何与“栈空间”有关；观念题则常见二分，说明学生把“名字出现”误当“无限重演”。这些前概念正是设计的燃料：错误不是要被clearing，而是要被照亮相。三、课程目标与评价对准知识与理解目标表述为可观察行为：学生能用自然语言给出某递归问题的两条定义，其一是“最小输入时结果是什么”，其二是“较大输入怎样依靠更小输入的结果”；能在给定代码中指出基准分支、递归分支、参数缩小方式与返回合成点；能解释调用栈帧中至少保存局部变量、实参值与返回地址三类信息。过程与方法目标指向推演能力：学生面对新问题时先写终止，再写缩小，再写合并，随后用增量输出验证三到五个实例；能把阶乘递归改写为循环，并说明两种写法在可读性、状态外显和峰值空间上的差异；能在汉诺塔三根柱的约束下，用移动序列证明子问题独立性。情感与价值目标不喊口号，落在程序伦理与工程节制：学生认同递归不是炫技，须用边界、复杂度与可测试性自我约束；愿意在团队中把抽象调用画成共同可读的图，接受同伴对边界遗漏的质询。评价证据与目标一一对应：课堂出口条收集“我定义boundary的方式”；即时纸笔完成斐波那契调用树修正；实验任务提交带缩进追踪的目录统计程序；单元后测嵌入一道陌生情境，要求不用现成模板完成“字符串回文切割的最少次数提示”的上半层递归框架，只评结构，不评最优。四、重点、难点与破解路径重点确定为递归定义的完整性，而非语法细节。难点分三层，层层设置脚手架。第一层是“自我指涉”的信任危机，破解用实体化演示：三张透明卡片分别写着f(3)、f(2)、f(1)，挂在黑板绳上，卡片转动代表进入调用，摘卡代表返回，学生眼见同一代码在不同卡片中拥有不同n。第二层是“返回合成”的时机错觉，破解用双色粉笔，向下展开写蓝色，向上合并写红色，颜色与执行方向绑定。第三层是“边界遗漏”的系统性风险，破解用故障库而非警告：教师投放五个只差一点就失控的程序，让各组认领病理，标注病灶，开出最小修复处方。由形象到符号的路径依次走“手势模拟—调用树—栈帧表—代码抽象”，由符号回到形象的路径安排“分形树绘制”作收束，避免只用数学函数造成递归等于数列递推的窄化。五、教学环境与资源准备机房按异质四人编组，座位不按成绩排队，而按“解释者、记录者、质疑者、运行者”轮换。每台机器预装Python解释器、turtle模块、过程可视化插件与本地评测脚本；投影端准备可逐帧暂停的调用栈动画；黑板右侧预留“危险带”，专贴错误递归；学习单采用三栏设计，左栏写定义，中栏画调用，右栏贴证据。资源不堆砌，务求每个材料只服务一个意图：阶乘用于直译，目录遍历用于真实，汉诺塔用于策略，分形树用于生成。网络访问限于局域网文档，避免学生复制外部答案造成“假通过”。教师端预设断点脚本，可在学生提交无终止递归时自动熔断并显示最近五层参数，保护课堂节奏不被死循环吞噬。六、整体流程与节奏控制本课按两课时连排设计，共九十分钟，中间保留八分钟弹性。第一课时解决“看见递归”，第二课时解决“用好递归”。开场三分钟用一叠办学籍档案盒制造悬念：要统计一盒中总页数，盒里还有盒，能否不开完所有小盒就先写出规则。学生被迫说出“若空盒则零，否则首页加子盒”这类雏形。随后十五分钟阶乘直译，二十五分钟调用栈实体化，十五分钟故障门诊；第二课时二十分钟目录任务，二十五分钟汉诺塔策略，二十分钟分形创作，十分钟对照迭代与递归，五分钟出口证据。节奏遵循低起点快进入、中段高频生成、末段公开评判；每一阶段都留出没说透的缝隙，让学生带着可回答的疑问走进下一步。七、导入：不开完所有盒子也能计数讲台放三层套盒，最外层贴A，中层贴B，内层贴C，C中放三枚计数片。教师不演示答案，只问：如果每只盒子都很深，不允许把头探到底，能否仍然宣布总数。学生自然提出“看标签”“称重量”“按规则估”。教师逼近一步：规则必须保证对任意套盒成立，且只许问一句话——你里面除了直接看到的，还有多少。这个问句把递归的两件必需品同时推出：直接可见部分给出平凡贡献，不可见底部的盒子被当作同类更小对象再次询问。板书逐步形成：count(box)若为空盒返回0；否则返回本盒散片数加count(下一盒)。此时不写代码，先让语言足够坚硬。教师强调“下一盒”总比“这盒”少一层包装，于是询问不会原地打转。导入不追求华丽，追求让递归从生活指挥链里长出来：班长不必认识全年级，只需知道每个小组报数；组长不必亲自点名，只需汇总副组长；责任沿结构下放，结果沿结构回收。八、活动一：把数学定义直译成程序从阶乘进入，是因为它几乎无背景噪声。黑板写出定义：0的阶乘为1；n为正整数时，n的阶乘为n乘n减1的阶乘。学生把两个句子映射成两个分支，约定函数名fact，参数为非负整数。代码极简：若n等于0返回1，否则返回n乘fact(n减1)。教师不急着运行，要求四人完成静态标注：圈出终止词，划出变小参数，框出乘法发生的位置。争论随之而来：“乘法在递归调用前还是后？”这句争论价值很高。学生起初按阅读顺序说先乘后调，实际追踪后发现表达式求值必须等fact(n减1)归来，乘法被压在返回途中。为让时机显影，运行带缩进版本：进入时按层数打印右箭头与n，返回时打印左箭头与乘积。屏幕出现“进四、进三、进二、进一、进零；出一返一、出二返二、出六、出二十四”的轨迹。教师只问一句：二十四在哪一刻第一次完整存在。学生答：最外层返回时。递归的“回来路上出答案”从此可被引用。九、活动二：让调用栈长出身体抽象讲解调用栈容易滑向名词解释，本课改做身体剧场。地面贴一条直线当作栈底，四名学生手持n等于4、3、2、1的牌依次站到线上，后来者站在更靠近门口的一侧，表示新帧压入。每人胸口挂记录板，写三项：我的n，我等谁，我回去后要做什么。当n等于1的学生再请到n等于0，边界触发，最靠近门口者先离场，把结果交给下一位；离场顺序形成清晰的后进先出。旁观学生把这个过程转写到栈帧表：帧号、实参、等待表达式、返回值、出栈去向。记录者发现，程序并没有很多份fact，只有一份代码被多个执行环境共享；质疑者追问环境差异来自何处，答案落到形参绑定与局部状态。此时引入限制：若每层都要记住一个待完成的乘法，深度很大时内存会被按住不放；相反循环版本用单个累积器滚动更新，峰值空间更省。递归与迭代的第一次比较不靠结论灌输，而靠身体站位后自然浮现。十、活动三：故障门诊与最小修复故障门诊把容易说教的边界变成可操作的病例。病例一没有基准：down(n)永远调用down(n减1)，学生观察到参数穿越零点奔向负数，修复是补n小于等于0时停止。病例二基准有过但不缩小：same(n)在n大于0时返回same(n)，病灶是参数不肯变，处方是每步必须接近边界。病例三缩小方向错误：up(n)在目标为10时调用up(n加1)，却写了n等于10停，起点大于10即失控，处方是依起点与目标关系选择递增或递减。病例四忽略非法输入：fact(负1)没有守卫，学生争论应在入口抛错还是约定返回，教师强调公开函数要把定义域说清，工程代码宁早失败不静默污染。病例五返回值丢失：过程里算了子结果却没有return，屏幕显示下探很深却得到空，学生由此记住“调用不是问候，返回才是交付”。每组只改一行或两行，必须说明为什么这叫最小修复；改动越克制，越能证明诊断准确，而非靠重写遮盖不懂。十一、活动四：目录大小中的真实遍历第二课时以真实任务开场：给定课程资源根目录，统计总字节数与文件数。学生先用系统经验描述手工办法，再看代码骨架：若路径是文件，返回大小与一；若是目录，初始化总量为零，遍历每个子项，把子项汇报累加；空目录自然返回零。此处递归对象是树而非线性链，调用树不再一条细线，而有分叉。关键教学点是把“for每个子问题”与“累加各子问题”分开：分支负责分派，汇总负责合成。学生运行带缩进日志，看到进入目录、下沉到子目录、撞到文件即返回、同级兄弟继续展开。教师引入权限错误与符号链接两处现实粗糙面：捕获异常让遍历不被单点失败击垮；对链接设置不回头策略，避免环状引用制造无穷树。这里没有把学生推进系统编程细节，只要求识别现实数据会弄脏理想定义，因此健壮性要在递归骨架外设护栏。评价标准为三句自述：我如何停止，我如何变小，我如何合并；小组互评时只针对这三句提问。十二、活动五：汉诺塔把策略说短汉诺塔难点不在移动，而在把移动的资格交给子塔。课堂先禁写代码，用圆片和三根筷做一轮三盘演示，要求每步说明“现在真正的大任务是什么”。学生发现，要把最大盘从甲到丙，必须先把上方两盘搬到乙，再把最大盘落位，最后把乙上两盘搬到丙。用语言凝固后，代码几乎成誊写：若只有一盘，直接从源到目标；否则先把n减1盘从源经目标到辅助，再移动最大盘，再把n减1盘从辅助经源到目标。教师特意让学生数三盘需七步、四盘需十五步，调用树呈二叉扩张，移动次数满足二乘前次加一。此处强调指数增长不是惩罚，而是结构本性；递归程序短，执行历史长，代码长度与运行代价不可混同。学生用纸带生成四盘移动序列，标出三次“大局转折”：最大盘何时终于可动。评价不看背下七步，而看能否在五盘情境中说出第一次最大盘移动前完成了什么。能说出这一点，策略即被理解而非模仿。十三、活动六：分形树中的生成与节制分形树用于把递归从正确性带入表现性。turtle从起点向上画主干，长度记为L；若长度小于阈值，抬笔返回；否则画线，右转一定角度，以更短长度递归画右枝，回转后再画左枝，最后回到分叉点。学生最先被图形吸引，随后发现美来自三个克制：长度按比率缩短，角度维持对称或受控扰动，深度设上限防过密。教师把参数调成不减小的badtree，屏幕迅速糊成一团；再把阈值取消，程序尚未出图已被停止。审美经验反身成为算法证据：生成力必须与终止力相配。拓展不要求人人相同，可提供三种口味：角度随机但限定区间，做出风感；左右枝长比例变化，做出倾向；颜色随深度递减，做出年轮。创作评价拒绝“好看就行”，要求作者说明每次递归保留了什么状态、放弃了什么状态；尤其要说明为何落笔前保存朝向、画完子枝恢复位置，这让“回到现场”与栈帧恢复建立可感联系。机房墙面最后展示十幅作品，标签不写姓名，只写基准、缩小率、最大深度，观者据标签猜图形，再与实物对照，递归参数由此获得可读性。十四、递归与迭代的对照审判对照不是宣判谁优谁劣，而是训练按需选择。以求和、阶乘、目录三类问题并排：线性数值递归常可翻成循环，换来稳定常数空间；天然树形遍历用迭代要写显式栈，代码更像把系统栈手工搬到堆中；汉诺塔若强行迭代，规则表达会失去“移上、落底、移回”的清明。学生填写对照表，维度过少容易失真，故设五列：问题形状是否自相似，终止是否直白，状态外显程度，峰值空间，失败时定位成本。讨论允许结论分歧，但每条结论须配一个场景。教师只给边界性提醒：深度不可控又要求实时响应，要慎用朴素递归；结构本身递归且原型阶段重视正确性，递归常先胜；性能敏感处再考虑尾调用习惯、显式栈或记忆化，但不在本课展开为竞赛技巧。这样处理守住选修课尺度：知道深处在哪，不必今天潜入。十五、常见误解的正面清算误解一，函数名出现在自己体内就是神秘魔法。清算方式：把函数名替换成“求助下一个规模”的标签，神秘感消失。误解二，先写递归分支才高级。清算方式：课堂统一逆序书写，先定停止，再构造缩小，最后才合成；顺序改变让失败率肉眼可见下降。误解三，打印结果等于理解结果。清算方式：禁止先跑，要求预言三行输出再运行；预言与屏幕不符时，以屏幕为师修改心智。误解四，递归一定慢。清算方式：拿小深度目录遍历与手工循环版本比可读性，再拿无边界汉诺塔说明指数来自问题而非递归语法。误解五，边界就是等于零。清算方式：展示回文判定用左右指针相遇，展示棋子步数用剩余步为零，展示目录用没有子项，终止形态随问题而变。误解六，加全局计数器就能解释一切。清算方式：同伴互查时见到全局变量只问一句“递归返回是否还需要它”，多数装饰性状态在追问中撤下。十六、课堂提问的阶梯设计提问分四层，层层可接手。事实层问：这段代码停在哪，参数每一步少了什么。解释层问：返回值在上层参与了何种运算，如果erasereturn会怎样。迁移层问：若把列表求和改成求最大值，基准是否仍为空列表对应零，若不是应改成什么。创造层问：给“嵌套括号深度”写一个仅八行的递归，要求能容忍空串。好问题要可败，坏问题只迎合成套。教师发问后坚持三秒静默，再指定尚未发言者；答错时不立刻纠正，转而请该生指定一个更可检验的小输入。课堂中设置“可撤回发言”制度，学生可在新证据出现后修改前答，黑板上保留旧答案并用箭头指向新答案，让学习被看见为轨迹而非瞬时对错。问题高峰期放在汉诺塔三盘与四盘之间，因为三盘可操作，四盘超出手感，刚好逼出口头递归。十七、板书与视觉语言的组织黑板划分三域，不改来改去。左域为定义，只放两条：停，缩；中域为调用树，蓝下红上；右域为危险带，贴病灶卡。当内容增加，教师不擦左域，宁压缩中域，因为定义是全课宪法。视觉符号规定统一：右尖括号表示进入，左尖括号表示返回，方框圈住当前最大盘，波浪线标可能存在环。颜色使用克制，蓝红之外不用第三色抢占注意。代码不上满屏，必要处只留骨架，变量名放弃单字母竞赛风，采用remaining、source、target、limit等可读词。学生在学习单中摹写同一套视觉语言，外显结构一旦统一，小组讨论可以越过个人笔迹差异，直接对准关系本身。十八、作业系统的分层与防复制作业分必做、选做、挑战三带。必做三题小而准：一是手写trace，给定mystery(n)在n小于2返n、否则返mystery(n减1)加mystery(n减2)，只追n等于5的树并计重复；二是把power(x,n)写成每次指数减半的递归，允许只处理非负整数，重点是缩小不止步进一；三是阅读目录统计代码，找出一个会造成重复遍历的链接情形并写防护。选做为现实改写：把家族称谓受限查询写成递归，输入两人关系链，输出是否在三服内，重在剪枝条件。挑战题为开放构造：设计一个函数，把任意嵌套列表拍平，但禁止用内置isinstance的现成范式，要求先定义“什么是原子”。防复制不靠搜题威慑，而靠提交三件不同源证据：代码、最小输入预言图、一次失败运行截图及修复说明。评分权重中，证据链高于最终答案，促使学生把过程留下。十九、评价细则与反馈话术评价采用四维二十点。结构定义五分，看两条递归陈述是否齐；执行推演五分，看能否画出三层以上轨迹；工程健壮五分，看边界、非法输入与异常态度；表达交流五分，看能否让同伴复述其规则。反馈话术避免空泛称赞，统一指向动作。若学生边界缺失，说“你的函数相信n永远会停在零，请给它一个不如愿的输入”；若返回丢失，说“你已经下到最深处，回来时空手，哪一层开始该接住东西”；若滥用全局，说“这个变量让所有层共用一个口袋，上一层凭什么相信它没被改脏”；若过早优化，说“先让结构站住，再谈速度，当前证据不支持改写循环”。同伴互评使用两张便利贴，绿色写“我复现了你的终止”，黄色写“这里我能让它失控”。被评者必须回应黄色贴，可选择接受或反驳，但反驳要带来新测试。反馈的尊严在于可检验，而非态度热烈。二十、差异化支持与扩展通道对基础薄弱学生，提供半填骨架而非空白页：基准已写，递归分支留两个空格，分别为更小参数与合成方式；允许先用三张卡模拟再进机房。对中等学生，撤掉模板，只保留“停缩合”三词；要求把每次错误命名，如负刺穿、原地踏步、空手而归，名字帮助调试。对学有余力者，不给更难的题海，而给解释责任：制作一页可讲给初中生的图解，说明为什么程序自己叫自己却不会乱；或研究同一代码在不同解释器中的递归上限，用受控实验说明限制不是语言羞耻而是资源治理。特殊需要学生采用语音口报执行轨迹与触觉圆片并行的方式，把抽象栈转为可排布的物件。所有支持共同遵守一条：降低入口，不降低概念；脚手架可拆，思想不能替做。二十一、教学风险与现场预案最大风险是无终止递归拖垮机房节奏，预案为评测脚本统一加深度哨兵，超过阈值抛出课程自定义提示，指回基准；同时在共享屏展示最近一次越界参数，变事故为教具。第二风险是汉诺塔步骤淹没策略，预案为规定凡人最多演示三盘，四盘以上只画“最大盘事件线”，不枚举全部。第三风险是分形课滑向美术课，预案为作品标签强制写三参数，缺参数不参与展示。第四风险是学生背诵“递归就是函数调自己”却不能用，预案为每节课尾声做一次陌生定义三十秒速判：判断新问题是线性递归、树形递归还是不适合递归，并说理由。第五风险是性别与经验刻板造成少数人霸占键盘，预案为运行者每十二分钟强制轮换，解释者不得连续两轮由同一人担任。预案写在教案不是悲观，而是给思维争时间。二十二、与前后知识网络的缝合向前缝合函数：形参是层与层之间的信封，返回值是信封回寄，局部性是各层互不偷看。向前缝合列表与字典：切片制造更小序列会付出复制成本，inquiry应说明切片表达清楚但未必最省；索引进阶作为后续注脚。向后连接分治：归并排序可把本课“停缩合”扩成“分治合”，但本课不抢跑，只在地基处留接口。向后连接树结构：目录是校园里真能摸到的树，文件与文件夹即节点与边；图与环在链接防护中提前投下一枚影子。横向连接数学归纳法：不正式证明，却让学生体验“最小成立，一步推下一步”的亲缘；教师在板书边写“归纳是证明里的递归，递归是运行中的化归”，一句话即可，不作哲学漫游。横向连接信息伦理：遍历目录引出权限边界，程序能到哪里不等于应该到哪里；能力、授权与目的三者要同时到场。二十三、课堂实录式关键片段重构某次试讲中，学生在fact(负1)上一致沉默。授课者没有给答案，把负一写在边界旁，问它会先撞见哪一行。多数人说先进入递归，因为没写n小于某数；随后一个平时少言的学生补刀：它永远不会撞见零，因减一离零更远。全班在那刻理解“停止条件必须落在必经之路上”。另一片段发生在汉诺塔，小组坚持先动大盘，理由是大盘最显眼。操作员被允许尝试，立即卡在“大盘压住一切”的物理事实；教师没科普规则，只问谁有资格第一个到目标柱。小组改口：不是最大盘先风光，而是最大盘要等到上空清空。把显眼与可动区分，比背步骤更有迁移力。分形环节中，一名学生把左右角设成悬殊，图形倾倒却好看，标签却写不出生成理由；同伴不批评丑美，只问你的程序每次结束了是否回到同一朝向。该生补上状态恢复，倾倒仍在，却从偶然变成可控风格。三个片段共同指向同一原则：课堂要保存学生撞上事实的瞬间。二十四、教师语言的减法与分寸本课教师话术做减法。少说“很简单”，它会羞辱还没看见的人；改说“现在只看n怎样变小”。少说“你们应该”，改说“这个输入会让哪一步违约”。少说“记住”，改说“把它画到能给别人复查”。少说“这就是递归”，改说“这个名字暂时叫足够小”。点评错误时不用人格词，专指条件：不是“你粗心”，而是“你的守护漏了负数开场”；不是“思路乱”，而是“合成在子结果回来前被使用”。沉默也算语言，三秒等待比立即救援更能维护思考权。教师还须忍住展示优雅版本，学生作品还毛边时就替换成大师写法，会偷走成就感；更稳妥的是并排陈列，让差异自己说话。分寸感的底线是：任何一句话若不能改变下一次运行，就晚一点说或不说。二十五、当堂检测与出口证据出口条只收三行，限时五分钟。第一行写：我给新递归问题找基准的方法。第二行写：判断参数真的变小的两个迹象。第三行写：本节课我想撤回的一个旧判断。收齐后教师当场抽取五张，不读名，只读命题，全班用手势判断是否可迁移。纸笔小测另设两题，第一大题给出hailstone序列片段，要求写出偶数减半、奇数乘三加一的递归外壳，不讨论猜想是否终止，只评参数与边界表达；第二大题给出错误flatten代码，病灶是把原子也当列表继续拆，