《用递归法解决问题》教学设计

庞霞+曹恒来

学习者分析

本节课的教学对象为高中二年级的学生。这个阶段的学生具有很强的自主意识，具备一定的探究能力，喜欢自己动手实践来获得新知。多次经历从问题到程序的思考过程，在面对现有软件无法解决的问题时能够编写程序解决问题。在此之前，学生已经掌握了循环、数组、自定义函数的使用，为本课的学习做好了充分的准备。

学习内容分析

《用递归法解决问题》是高中选修教材《算法与程序设计》（科教版）第三章“算法的程序实现”第五小节的内容。在本课学习之前，学生已经学会了用循环的方法来解决问题，然而循环的方法往往并不会那么清晰地描述解决问题的步骤，递归法则可以非常直白地描述一个问题的求解过程，因此递归法也是最容易实现的算法。

递归的基本思想是把规模大的问题转化为规模小的相类似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一种方法，所以就产生了调用自身的情况。递归是利用系统的堆栈保存函数中的局部变量来解决问题的，因为函数调用的开销比较大，递归常常会带来效率问题。本节课学生不仅要学会用递归法解决问题，更重要的是领会递归思想的精髓。递归思想是计算机学科中的核心技术思想之一，其本质反映的是一种将复杂问题简单化的思维方法。

学习目标

知识与技能目标：理解递归的含义，找出递归问题中缩小问题规模的递归处理方法及递归结束条件，了解递归算法的优缺点。

过程与方法目标：能用程序实现递归算法，学会用简单模式解决复杂问题的方法。

情感态度与价值观目标：领悟递归思想，体验递归思想在实际生活中的应用。

教学重点、难点

重点：分析递归结束条件及缩小问题规模的方法，以及递归算法的程序实现。

难点：递归算法的程序实现。

教学策略

呈现斐波那契数列问题，由学生比较熟悉的递推法入手，针对问题描述中的不严谨之处，引入递归定义及其关键因素——递归结束条件和缩小问题规模的递归处理。在递归的学习过程中，学生通过阅读代码、尝试模仿、归纳提炼、拓展应用等环节逐渐完成知识的内化并达到应用、迁移的目的。最后，学生通过实践比较，体验递推、递归两种方法的运行效率，并分析造成递归法运行效率低下的原因，学会辩证地看待问题，在应用递归思想时逐渐形成一个意识——学习程序设计不仅仅是为了编程解决问题，更重要的是形成正确的解决问题的方法和态度。

教学过程

1.呈现问题，初识递归

某电子购物平台在15周年庆之际特别推出了签到送积分活动。活动具体规则如下：从6月1日到6月15日，第1天、第2天签到均可领取1个积分，第3天签到可领取2个积分，第4天签到可领取3个积分，第5天签到可领取5个积分……请问，小丽从6月1日起就坚持每天签到，那么，6月15日那天她将领到多少积分？你能找出这15天每天所领积分之间的关系吗（如下页图1）？

观察图1，可以发现：第1天和第2天都只有1个积分，从第3天到第15天，每天领取的积分数就进入了一个重复的计算过程，即每天领取的积分是前两天的积分之和。为了存放每天领取的积分数，可以定义一个数组Fib（15），该数组中，Fib（1）=1，Fib（2）=1，而从第3天开始的重复过程，可以利用循环来完成，代码如下：

刚才计算的这一组数：1、1、2、3、5……是一个典型的斐波拉契数列，在解决这个问题的过程中，借助数组，从已知条件出发，利用循环的方式按照一定规则从前往后递推，最后得出了结论，这种解决问题的方式称之为递推法。然而，在描述这组数时使用了“……”，在数学里经常看到这种写法，实际上这种写法并不科学，是数学表述中常见的不精确性。因为它的意义依赖于人对省略号的理解和共识。所以，斐波拉契数列还可以这样定义：

这种定义方式将问题分成了两种情况：一种是可以直接求出结果；另一种是把问题分解成规模更小、与原问题相同解法的小问题。在用函数实现时，因为解决大问题的方法和解决小问题的方法是同一个方法，所以就产生了函数调用它自身的情况，我们称之为递归法。递归通常使用自定義函数的形式来实现。这样，求斐波那契数列就变成了一件极简单的事情。

设计意图：循环的方法并不会那么清晰地描述解决问题的步骤，针对问题描述中的不严谨之处，给出了一个较科学的定义。由斐波那契数列的定义引入递归的概念，并给出对应的递归程序代码，以便学生理解递归代码并深刻感受递归法描述问题的简洁、直白。

2.模仿尝试，体验递归

活动1：请大家模仿上例，分别完善程序，尝试用递归法解决下面三个问题。

（1）求阶乘。阶乘的递归定义如下：

（2）计算年龄：有5个人坐在一起，小华问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁……一直问到第1个人，他说自己10岁。你能帮小华算出第5个人多少岁吗？

递归定义：

（3）汉诺塔：如图2所示，你能借助②号杆将①号杆上的盘子移动到③号杆上而不改变盘子的次序吗？最少移动多少次？移动规则：每次只能移动一个盘子，大盘不能放置在小盘之上。

释疑：可将n-1个盘子进行捆绑，那么整个移动过程便“简化”为“三步”：

a.将这n-1个盘子从①移动到②，需要hanoi（n-1）次；

b.将剩下的最后一个大盘移动到③，需要1次；

c.将②上的n-1个盘子移动到③，又需要hanoi（n-1）次。

因此，可通过如下的递归定义来缩小问题规模：

Private Function hanoi（ByVal n As Integer） As long

End Function

展示学生程序，调试运行并分析其缩小问题规模的递归处理办法和递归结束条件，以及函数调用的方式。

设计意图：以半成品代码填空的方式，有目的地将代码的核心部分留白，引导学生从不同角度进行模仿，尝试使用递归的方法解决问题。

3.归纳提升，认识递归

通过实践，可以总结出递归实现的基本模式，如图3所示（以斐波那契数列的递归程序为例）。

小结：①递归法通过自定义函数来实现；②函数体内通过分支来判断是否满足递归结束条件，不满足则进一步缩小规模，递归处理。

设计意图：进一步归纳总结，对所学知识进行提炼，逐步形成递归解决问题的基本模式。通过对具体的语言、算法中发现的解决问题的规律进行提炼，更有助于学生对知识进行内化，并能够将此规律运用于解决新的问题，从而真正达到应用、迁移的目的。

4.实例拓展，应用递归

掌握了递归法解决问题的一般格式，学会分析递归结束条件和缩小问题规模的表达式后，再利用递归法来解决一些问题。

活动2：求两个数的最大公约数。辗转相除法，又名欧几里德算法（Euclidean algorithm），是求两个正整数的最大公约数的算法。设两数为a、b（a>b），求a和b最大公约数gcd（a，b）的步骤如下：r1=a mod b（r1≥0）。如果r1=0，则gcd（a，b）=b；如果r1<>0，则r2=b mod r1（r2≥0）。如果r2=0，则gcd（a，b）=r1，若r2<>0，则继续用r1除以r2，……如此重复求除数与余数的余数，直到能整除为止。

递归定义：

Private Function gcd（ByVal a As Integer，b as integer） As integer

End Function

提示学生分析递归结束条件和如何缩小问题规模，注意递归函数的书写形式。

设计意图：学以致用，利用学生熟悉的数学问题以降低学习的难度。活动2与活动1相比，其难点在于函数的参数变成了两个，在学生分析问题时教师应当给予适当的引导。

5.实验比较，再认递归

活动3：递推法和递归法的实验比較。

（1）用递推和递归分别求Fib数列的第15、25、35个数，测试大致运行的时间，比较两种算法的效率（如上表）。

（2）分析原因。以Fib（5）的计算情况为例，尝试完成图4所示的调用关系，直至递归结束。

通过这幅图可以发现在程序运行过程中存在着大量重复的函数调用，且参数越小，调用次数越多。正因为大量重复的调用，递归函数的使用相当耗费计算机资源，运行效率较低。

递归法虽然运行效率较低，但它的程序结构清晰、易懂，是循环无法替代的。不仅如此，递归思想反映出的一种跳跃性的思维方法也为我们打开了解决问题的全新思路。递归思想启迪我们要善于发现事物的整体与局部间的规律，学会从不同的视角去理解问题的整体和局部。

在我们的学习、生活中也存在着很多递归思想的应用。图5所示的就是用递归法绘制的分形图。

在生命科学中，当以不同的放大倍数观察小肠结构时，从左到右较大的形态与较小的形态之间存在着自相似（如图6）。

设计意图：通过实践对比，学生感悟到递归的运行效率问题及其运行效率低下的原因。虽然递归运行效率不高，但其跳跃性的思维方式、用简单模式解决复杂问题的思想却广泛地存在于程序设计乃至其他学科中。本环节实现了基础知识到思想方法的提升。

点 评

长期以来，我国中小学非常注重“双基”教育，然而，随着时代的发展和知识的激增，基础知识和基本技能可能很快就会老化、过时，无法构成学生未来发展的基础。反之，学生在一门课程学习中形成的相对稳定的思考问题、解决问题的思维方法和价值观——学科思维，则会伴随学生一生。起源于计算机科学的计算思维，不仅是运用计算机科学的基础概念求解问题的方式，更是理解世界的方式，甚至是做事、探究、协作的方式，充分彰显了基础教育课程的基础性特征，从而构成了信息技术课程思想的完整体系。

作为计算思维的一种关键思想，递归首先是一种解决问题的方式，其核心是按照一定的规则不断缩小问题规模直至递归结束条件出现，关键是要从整体上把握，通过“递”把主问题分解成子问题，而“归”就是利用子问题的解逐步向上求解，根据这样的思路可以利用相对简单的方法来解决复杂的问题。本节课教师十分注重引导学生构造问题的递归定义，寻找到了递归定义，基本上就可以直接翻译成程序了。求斐波那契数列、阶乘和汉诺塔三个问题，由教师直接给出递归定义，而求最大公约数则在算法分析的基础上引导学生自主尝试定义递归，进而拓展到分形图的绘制。生命科学中具有分形特征的小肠结构，引导学生运用递归思想发现事物的整体与局部间的规律，体会递归思想在社会意义和教育意义上的普遍价值。

另外，程序设计具有强烈的工程属性，对同一问题常会得到许多合理而正确的不同程序。在寻找可能的解决方案时，需要对各种方案作出评价和选择，对所做选择的优点和缺点应有清醒认识。这一点在递归程序设计中体现得尤为明显，递归描述的程序很容易阅读和理解，却也有一个很大的缺陷——其中可能存在着大量的重复计算。许多学生可能认为，今天的计算机这么快，多算几次花不了多少时间，本节课通过试验，对比递推法和递归法计算不同数值斐波那契数列所耗费的时间，提高了学生对计算“复杂性”的认识。

当前，程序设计教学中“个性化”方法比较严重，同一个算法在不同问题中的描述往往是不同的，学生即使编写了“大量”的程序，也无法迁移到相似问题的解决过程之中。本节课，教师通过对多个个别程序的归纳，形成递归解决问题的基本模式，并推广到更广泛的问题解决与应用中，这种基于模式建构的程序设计学习有助于学生建立良好的程序设计思维和方法，也有助于学生对知识进行内化。