深度学习算法，提升计算思维——以“青蛙跳台阶”的递归算法为例

郭芮 福建省厦门第二中学

●当前高中信息技术计算思维培养的诉求

《普通高中信息技术课程标准（2017年版）》（以下简称“新课标”）的颁布实施与新教材的使用，使普通高中信息技术教学由传统的注重技能实操转向更加强调学生计算思维等核心素养的培养。笔者结合新课标的要求，梳理出计算思维包含的几个重要要素：分解、分析、抽象、建模、算法设计、自动化。在教学中，教师可通过算法设计和编程实践来培养学生对这些要素的理解和应用，以培养他们的逻辑思维、创新能力和问题解决能力。

●案例背景

1.递归问题

递归问题是指在解决某个问题时，可以通过调用自身来实现的问题。递归问题通常需要满足两个条件：①基本情况。定义递归结束的条件，即最简单的情况，无需再次递归调用自身，直接返回结果。②递归关系。将原问题分解成一个或多个规模较小的子问题，并通过递归调用自身来解决这些子问题。

2.递归问题与计算思维要素的关联

递归问题与计算思维要素之间存在紧密的关联，具体如下表所示。

●案例描述

本文以“青蛙跳台阶”问题为例，渐进式地分为简单、中级、复杂三种情况。“简单”问题引出递归算法。“中级”和“复杂”问题考查学生对递归算法的理解和运用。

1.创设情境，趣味导入

活动1：一只青蛙一次可以跳上一级台阶，也可以跳上二级台阶，求这只青蛙跳上n级台阶总共需要多少种跳法。

（1）问题分解（如下页图1）

图1

当n=1时，只有1种跳法；当n=2时，有2种跳法；当n=3时，有3种跳法；当n=4时，有5种跳法；当n=5时，有8种跳法……

（2）问题分析

提取重复逻辑：1，2，3，5，8……当n=n时，可以用倒推的方式来分析问题。青蛙跳上最后一级台阶的方式只有两种情况，要么是1级跳，要么是2级跳。若青蛙用1级跳的方式跳到最后一级台阶，那么它前面跳的方法共有f(n-1)种；若用2级跳，则共有f(n-2)种。所以，两种情况加起来就是总种数：f(n)=f(n-1)+fn(n-2)（n≥2）（终止条件：n=1，n=2）。

（3）抽象建模（如图2）

图2

（4）编程实现（如图3）

图3

设计意图：借助游戏问题引入课堂教学，活跃课堂气氛，迅速集中学生的注意力。在问题解决中，自然引出本课课题——递归法。

2.举一反三，理解递归

活动2：一只青蛙一次可以跳上一级台阶，也可以跳上二级台阶……还可以跳上n级台阶，求这只青蛙跳上n级台阶总共需要多少种跳法。

（1）问题分解

通过上一道题的练习，学生已经对递归算法有了初步认知，并且理解抽象的递归表达。所以用f(n)表示青蛙跳上n级台阶的跳法数，设定f(0)=1。

当n=1时，有一种跳法，f(1)=1。

当n=2时，有两种跳法，一阶跳和二阶跳：f(2)=f(1)+f(0)=2。

当n=3时，有三种跳法，第一次跳出一阶后，后面还有f(3-1)种跳法；第一次跳出二阶后，后面还有f(3-2)种跳法；第一次跳出三阶后，后面还有f(3-3)种跳法：f(3)=f(2)+f(1)+f(0)=4。

当n=4时，有四种跳法，第一次跳出一阶后，后面还有f(4-1)种跳法；第一次跳出二阶后，后面还有f(4-2)种跳法；第一次跳出三阶后，后面还有f(4-3)种跳法，第一次跳出四阶后，后面还有f(4-4)种跳法：f(4)=f(3)+f(2)+f(1)+f(0)=8。

……

（2）问题分析

提取重复逻辑：当n=n时，共有n种跳的方式，第一次跳出一阶后，后面还有f(n-1)种跳法；第一次跳出二阶后，后面还有f(n-2)种跳法；第一次跳出n阶后，后面还有f(n-n)种跳法，最终得出公式为：f(n)-f(n-1)=f(n-1)→f(n)=2*f(n-1)(n≥2)（终止条件：n≤1）。

（3）抽象建模（如图4）

图4

（4）编程实现（如图5）

图5

递归法解决问题的方法：①二要素——递推与回归。②找到结束条件。③递归算法的实现方式（递归算法是数值层层调用实现的，函数先由上向下调用，当达到最底层后，再将数值层层向上返回）。④程序结构——函数和分支结构。函数定义递归问题本身，分支结构解决终止条件和调用规律。

设计意图：在前一个活动实践的基础上，给出递归算法解决问题的方法，对学生已经构建好的模型框架进一步梳理，帮助学生形成递归算法解决问题的思想和方法。

3.拓展提升，深度学习

活动3：一只青蛙一次可以跳上一级台阶，也可以跳上二级台阶……还可以跳上m级台阶，求这只青蛙跳上n级台阶总共需要多少种跳法。

（1）问题分解

结合上一道题的思路，得出：f(n)=2f(n-1)-f(n-m-1)。

（2）问题分析

分析1：如果n≤m，因为只能往上跳不能往下跳，所以大于n的都不可以跳，那么这个问题就直接退到问题2。

分析2：如果n＞m，要想跳到n级台阶，可以从n-1级跳一步上来，或者从n-2级跳两步上来……或者从n-m级跳m步上来，所以可以找出递归公式。

（3）抽象建模

当n=m时，和上一题的解答思路一致。当n＞m时，f(n)=2f(n-1)-f(n-m-1)。

（4）编程实现（如图6）

图6

设计意图：经过前面的活动，让学生基本掌握递归法解决问题的方法。

●教学反思

1.明确新课标要求，把握案例设计

根据新课标中对计算思维教学的建议，通过递归算法的学习让学生从实际问题出发，感知递归、发现规律；理解递归算法的基本思想，运用恰当的方式分析和抽象建模，梳理出问题结构，并通过恰当的程序语言和程序控制结构实现递归算法。因此，本案例通过由浅入深的青蛙跳台阶问题，让学生在一个个活动中反复体会递归问题“来”与“去”的过程，体验使用Python语言实现递归程序设计的方法，感受算法效率的重要性，增强学生运用算法思想解决实际问题的能力，培养计算思维。

2.分层任务设计，促进深度学习

深度学习是指学生的已有经验或知识与新的经验和知识之间产生了连接，继而获得深层次的学习动机、亲身体验和高阶思维，对学生产生深远影响的学习。在本案例中，学生在同一情境、不同难度的任务驱动下，构建和迁移递归思想，从而逐渐形成应用递归算法与程序设计解决现实问题的高阶思维能力。

3.依托数字化平台，助力计算思维培养

算法是抽象后的概念，递归算法又是不断拆解和回归的过程，更加抽象。对于学生而言，在头脑中将拆解和回归的过程复现是比较困难的，因此，教师可引导学生借助数字化平台可视化观察递归算法的过程、在线检验编程结果、查找更好的解决方案等，在帮助学生提高信息意识的同时，强化学生的数字化学习能力，助力计算思维培养。

4.完善教学评价，培养计算思维

教师可以借助数字化平台中的“考试”“抢答”“作业”等功能，对学生的课前基础、课堂成果、课后练习、阶段性学习等进行综合评价。通过完善教学评价体系，帮助学生了解自身的优劣势，培养计算思维。

●结束语

本文以递归算法为例，通过趣味的游戏问题，详细探讨如何在教学实施过程中针对问题分析开展“抽象”，并在“抽象”的基础上实现“建模”，最终培养和发展学生的计算思维，完成对算法大概念核心原理的理解，并在一定程度上反作用于数学关键能力的培养，以推进拔尖创新人才培养的持续、健康发展。