基于深度学习的程序设计教学实践探究

赵倩倩

摘要：迭代法与递归法的比较在2020版教科版高中信息技术教材必修1第四单元“4.3 非数值计算”中的拓展知识与选择性必修1中的“3.1 迭代与递归”中均有所涉及，很多学生难以透彻理解二者的关系，导致在解决实际问题时不能灵活应用。作者通过对典型案例的深入探究，使学生明确迭代法与递归法实现过程与执行效率及应用方面的异同，在解决问题时能辨证地看待与应用，达到了深度学习的效果。

关键词：深度学习；递归法；迭代法；比较

中图分类号：G434  文献标识码：A  论文编号：1674-2117（2023）11-0052-04

程序设计课深度学习的困境

深度学习是指在真正理解一个知识点的基础上，能够在新问题情境下灵活迁移运用该知识点，快速找到解决思路和方法的一种学习。它以联系和理解为主要特征，鼓励学生积极地反思、探索，发展学生分析、应用、评鉴和创造等高阶思维能力。[1]在当前高中程序设计与算法的课堂教学中，部分学生存在“听讲时都会，解决实际问题时却不知从何下手”“编程解决问题时没有考虑程序的运行时间”“没有评价算法执行效率的意识”等问题。出现这些问题的原因有两方面：一方面是由于程序设计的核心知识——算法的学习是高阶思维的形成，难度较高，学生没有真正理解、理清知识的内涵、外延及相近知识之间的关系，不能熟练应用。另一方面是缺乏深度的教学使学生体验得不深刻、思考得不深入、理解得不透彻。针对问题及原因，笔者尝试以教科版高中信息技术教材必修1第四单元“4.3 非数值计算”中的拓展知识与选择性必修1中的“3.1 迭代与递归”中都涉及的相似算法——迭代法与递归法的比较为例，探讨如何进行基于深度学习的程序设计教学实践。

基于深度学习的程序设计教学实践

迭代法与递归法在程序设计中应用广泛，是排序、搜索、查找、分治等经典算法的基础，但对高中生来说，刚开始学习时往往难以理解二者的异同。因此，在教学实践中，教师应明确促进深度学习的教学目标，注重引导学生的高阶思维投入，并从具体的案例开始，探究分别使用迭代法与递归法解决同一问题，使学生深入理解两种算法的执行过程与使用方法；通過对时间与空间消耗的分析来比较两种算法的执行效率，在此基础上触发学生深度思维，辩证地看待与使用算法解决实际问题。

1.寻找最近发展区，促进深度学习的开启

教师提出问题：斐波那契数列是指像1、1、2、3、5、8、13、21……的数列，即后一项是前两项之和，在数学中该数列定义为：f（1）=1，f（2）=1，f（n）=f（n-1）+f（n-2）（n＞2）。请说出数列的第20项数值。通过问题引入，学生在回顾数学知识的同时，体会当人工推算满足不了需求时，就要借助编程计算。这里有两种方法：一种是从已知值开始，通过递推关系式一步一步地推出所求未知项的值，这种方法即迭代法。另一种是从所求未知项出发，通过调用函数，倒推至初始项，再代入初始项的值一步一步回推而求出未知项的值，这种方法即递归法。

在教学中，教师可以借助数学中经典数列问题的定义，从学生的最近发展区入手，激发学生学习兴趣并思考，由简单的数学推算过渡到利用递推关系式编程计算，由浅入深，使学生的思维由数学思维过渡到算法思维，促进深度学习的开启。

2.解构算法核心概念，建立深度学习的联接

深度学习的达成需触发学生的深度思维，而深度思维首先应聚焦、解构概念的内涵与外延。迭代法又称辗转法，是从初始值开始多次对过程进行重复，每一次迭代得到的结果都会被用来作为下一次迭代的初始值，以达到所求目标。递归法是指函数直接或间接调用自身的一种方法，其基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。

（1）从问题分解与构造的角度看迭代与递归

迭代法和递归法都是将大的问题分解成很小的问题直到小的问题能够解决的方法。迭代法是从已知开始，即f（1）与f（2），通过循环结构实现反复替换，在反复替换中达到解决问题的目的，它有三个构造过程：①确定迭代变量的初始值；②建立递推关系式；③迭代的结束条件，不能让迭代无限重复。递归法则是从未知开始，通过反复调用函数直到遇到边界f（1）与f（2），然后逐层返回获得结果，它有两个构造过程：

①递推——通过逐层函数调用实现；②回归——当获得最简单的情况即数列的初始项f（1）与f（2）后，逐步返回，依次得到问题的解。递归法函数调用过程如图1所示。

（2）从形式化表达的角度看迭代与递归

实现迭代法的循环控制和实现递归算法的函数调用与选择结构，都是形式化表达方式，它们在程序设计中已存在标准的模型，可以方便地将复杂问题的解决过程进行形式化描述。这里要注意f1，f2=f2，f1+f2是Python语言中的元组赋值方式，是对数列元素反复替换求解的形式化表示，同时创建两个元组，然后将上一步的（f1，f1+f2）元组的值赋给当前的（f1，f2）元组，就实现了多个变量值的替换与更新。表1所示为对使用迭代法与递归法解决斐波那契数列问题的两个方面进行的比较。

通过对迭代法与递归法核心概念的解构，引导学生对知识进行归纳与整理，促进学生理解并熟练掌握两种算法在实现过程与形式化表达方面的异同，从而建立深度学习的联接。

3.分析算法的执行效率，促进深度理解

教师可以对算法执行过程层层设疑，使教学目标更为具体化，进而为实现深度学习的目标提供可能。教师先请学生思考在使用迭代法与递归法分别计算fib（7）时，fib（3）计算了几次。学生观察程序发现在用迭代法计算时，循环体内执行了5次赋值运算，运行时间只随循环次数的增加而增加，每次循环结束后变量的值将直接被替换更新，不占用额外空间。而在用递归法计算时，学生借助递归函数调用思维导图（如上页图1），可以看到每个递归调用都触发另外两个递归调用，fib（3）被调用计算了5次。当n较大时就产生了大量的函数调用，而函数调用时参数压到堆栈中，需为变量分配内存空间，每深入一层都要占用一块数据区域，产生许多额外的时间与空间消耗。最后，借助timeit模块函数来统计程序运行所消耗的时间，随着所求项数n的变化，两种算法的时间消耗与空间占用对比如表2所示。

通过上述比较与分析，教师再引导学生进一步总结两种算法的时间消耗与空间占用方面的特点，学会分析算法的执行效率，层层深入，促进对两种算法原理的深度理解，从而在面对实际问题时能合理地选用算法，辩证地看待与使用迭代法和递归法解决问题。

4.设置变构应用情境，巩固深度学习的效果

深度学习往往意味着高难度的学习，根据认知负荷理论，深度学习知识本身的难度会增加学习的内在认知负荷。[2]因此，教师可以通过针对性的巩固练习，设置变构应用情境，将解决同一问题的不同算法代码实现进行对比，同时对相同算法解决不同问题的代码进行对比，做到算法与应用结合、代码知识与应用结合，加强学生对应用这两种算法编写代码解决实际问题的理解，从而突破难点。

以“求阶乘问题”的两种算法实现及比较为例，求正整数n的阶乘。依据数学中对阶乘的定义（一个正整数的阶乘是所有小于及等于该数的正整数的积，0的阶乘为1），引导学生对问题进行分解与构造，写出n的阶乘的递推关系式n！=n*（n-1）*…*1。在用迭代法实现时需确定初始值与终止条件，使用循环结构进行数据的更新替换；在用递归法实现时需确定递归出口与定义递归调用函数。进一步设置进阶变构应用，以“爬台阶问题”的两种算法实现及比较为例，假设爬台阶有两种方式，一种是一步迈1级台阶，另一种是一步迈2级台阶，请问爬n级台阶一共有多少种方式。提示学生从问题的分解与构造、形式化表达方面着手，分析问题的求解步骤。定义求解爬n级台阶的函数为num（n），如果第一步迈1级，那么剩下的n-1级台阶有num（n-1）种走法；如果第一步迈2级，那么剩下的n-2级台阶有num（n-2）种走法，提取算法的递推关系式：num（n）=num（n-1）+num（n-2）。当n=1时，num（1）=1，当n=2时，有2种走法即num（2）=2，这两个条件即为迭代法的初始值、递归法的边界。这两个问题的迭代法与递归法的Python实现代码如上页表3所示。

对比以上问题的两种算法实现代码，学生会发现迭代法与递归法都需要重复执行某些代码。迭代是重复执行的过程，目的是逼近所求结果，通常使用计数器结束循环；递归是重复调用函数自身，当遇到满足终止条件的情况时逐层返回。

再以必修1“4.3 非数值计算”中的拓展知识“汉诺塔游戏”为例，教师可以从数值计算过渡到非数值计算，发散学生思维。通过分析当n大于1的时候，可以考虑先将上面n-1个圆盘看作一个整体通过A移动到B上，再将A上的最后一个圆盘移动到C上，最后将B上的n-1个圆盘通过A移动到C上，对n-1个圆盘进行递归调用直到n=1时为递归出口，只需直接将A上的圆盘移动到C上即可。递归实现代码如图2所示，其中递归调用语句后还有非递归调用语句print（），如直接用迭代法解决将增加实现难度，导致代码不易读。

所以说，当一个问题相当复杂，难以根据当前所学知识应用迭代法实现时，递归实现的简洁性便可以弥补它所带来的运行时的开销。同时，教师要引导学生在解决实际问题时具体问题具体分析，对于规模小的问题，可根据自己的偏好来选择算法，但对于大型问题或特殊问题就需要综合考虑算法的执行效率与可读性。这样，通过知识整合、横向与纵向对比，达到了提升批判性高阶思维能力和解决复杂问题能力的教学目标，促进了学生对迭代法与递归法的灵活迁移运用，巩固了深度学习的效果，激发了学生进一步探究与学习算法的兴趣。

结语

通过对两种算法执行效率的比較，可以引导学生对程序执行过程进行反思，这是算法不断优化思想的体现，并促使学生在反思与优化中发现迭代法与递归法解决问题的特点，这样既使学生全面掌握了知识，又发挥了学生的自主性，锻炼了评价算法的能力。这些都是促进学生深度学习的途径，也是发展学生计算思维的要义所在。

参考文献：

[1]卜彩丽.深度学习视域下翻转课堂教学理论与实践研究[D].西安：陕西师范大学，2018.

[2]乐会进，蔡亮文.混合教学模式何以促进深度学习——基于翻转课堂的研究[J].中国信息技术教育，2018（08）：143-147.

本文系2019年度湖北省教育信息技术研究与教育科学规划重点课题“基于MOOCAP的大学先修课程高中实践研究——以程序设计先修课为例”（课题编号：2019ZA57）研究成果之一。