递归算法课堂教学设计探讨

王琳 张学波

摘要：结合大学计算机基础课程的开设情况，针对课程中一些不易理解且难以讲解的知识点，如递归算法，本文结合递归算法经典示例汉诺塔问题，探讨了一个新的课堂教学设计，并应用于实际的教学中。首先如何引入课堂，抓住学生的兴趣，然后提出问题，思考递归算法和汉诺塔之间的关系，并通过互动环节，让学生动手尝试挪动汉诺模型，学会使用计算思维进行思考与分析。最后依据递归原理，用Python语言编写汉诺塔的递归函数。在实际教学过程中，该课堂设计提高了学员学习的主动性和参与度，提升了课堂教学质量和学员的计算思维能力。

关键词：课堂设计;递归算法;汉诺塔问题;可视化;turtle

中图分类号：TP311        文献标识码：A

文章编号：1009-3044（2021）27-0208-02

“大学计算机基础”是大学本科教育的第一门计算机公共基础课程，课程的主要目的是从计算机应用、计算机系统理解和计算思维培养三个方面提高学生的计算机应用能力。从2008年开始，以“计算思维”的培养为主线开展计算科学通识教育，逐渐成为国内外计算机基础教育界的共识。

基于这种共识，“大学计算机课程”选择Python作为实践语言，将信息编码、微机原理、操作系统、网络、数据库等知识既作为教学内容，又作为计算思维求解问题的研究对象加以实践。希望通过这种问题求解的学习和实践过程，在培养学生理解计算机基础知识的同时，能有意识地将计算思维的方法和技能运用在各自专业的学习中，能解决具有一定难度的实际问题。

作为课程的重难点之一的第三章，即计算思维这一章，要求学生在理解计算思维的同时，要了解一些典型算法，并能够掌握典型算法的Python实现方法。本文以递归算法为例，探讨如何更好地进行课堂设计。

递归算法作为经典算法之一，虽然实现较容易，但理解起来有一定的难度，为了让学生能更直观的理解递归算法，课程专门设置了一个递归算法经典示例汉诺塔问题，利用Python的turtle库实现汉诺塔的可视化，帮助学生从抽象的理论思维过渡到直观的可视化应用。

1 如何引入课堂

教师在讲解汉诺塔问题之前，可以借助动画的形式展现可视化的汉诺塔，便于较快地抓住学生的注意力，提高学习兴趣;引导学生在观看动画的同时，思考汉诺塔中的每个盘片是怎样移动的？利用Python语言如何编写程序实现它的可视化效果？

带着这些问题，教师引出汉诺塔问题的传说和移动规则。汉诺塔问题来源于一个古老的传说， 传说印度教里有一个神叫梵天，梵天在创造世界的时候做了三根金刚石柱子，其中在 1号柱子按大小顺序套着64个黄金盘片，梵天要求僧侣们把这64个盘片借助于中间的2号柱子移到3号柱子上，按原来的样子摆放好。盘片在移动的过程中要遵守两个规则：一次只能移动一个盘片;大盘片不能叠放在小盘片的上面。

讲解完规则后，继续借助于传说，将学生的兴趣和好奇心拉至最高点。如果按照这样的规则进行搬移，梵天预言，一旦这些盘片完成搬移，世界将会毁灭。该结论一出，学生们纷纷表示怀疑;在这个互动环节，可以让学生大致算一算，假如搬完所有盘片需要多长的时间？经过计算，搬完所有盘片需要移动的次数是264-1=1.8×1019次，也就是1800亿亿次，如果每秒搬动一次，则需要584，942，417，355年，也就是五千亿年！拿五千亿年和我们人类的长河几百万年相比，要搬完64个盘片是不可能的。

通过证实结论，学生的疑虑消除了，此时讲解思路180度转弯，视角回到当今的计算机时代、数据化时代，人工不能完成的事情是不是可以借助于计算机实现呢？借助于计算机，利用抽象化、自动化的方式将实际问题进行转化，从而解决这个问题，这正是大学计算机基础课程的目的，利用计算思维解决各领域的实际问题。

2 如何引导学生利用计算思维分析递归算法和汉诺塔之间的关系

计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为。它包括了涵盖计算机科学之广度的一系列思维活动。当我们必须求解一个特定的问题时，首先会问：解决这个问题有多么困难？怎样才是最佳的解决方法？计算机科学根据坚实的理论基础来准确地回答这些问题。表述问题的难度就是工具的基本能力，必须考虑的因素包括机器的指令系统、资源约束和操作环境[1，2]。

教師可以借助于提前准备好的教具-汉诺塔模型，让学生以分组的方式动手尝试简单汉诺塔的移动过程，并展开小组讨论。在实践的过程中，有些小组成员思维反应较快，能够完成5-6层汉诺塔的移动，有些小组陷入了移动的僵局。无论是完成快的小组还是慢的小组，都很难说清汉诺塔和递归算法之间的关系。

带着这个问题，教师进行示范，从一个盘片的汉诺塔开始摆起，当摆到两个盘片的汉诺塔时，学生思考总结出移动三部曲，先移走上面的小盘片至中间柱，再移动大盘片至右侧的目标柱，最后移动小盘片到目标柱。利用移动三部曲，在挪动三个盘片的汉诺塔时，可以把上面的两个小盘片看成一个整体，完成三部曲，再将整体还原为两个小盘片，两个小盘片的移动刚刚已经做过。这时，学生恍然大悟，可以利用三部曲尝试移动3个甚至更多盘片。最后，教师进行总结，借助于五个盘片的汉诺塔，并用递归图更好地诠释了汉诺塔的三部曲移动正是借助了递归算法。

分析完汉诺塔和递归算法之间的关系后，整理思路，依据递归算法原理，设计求解汉诺塔问题的函数hanoi（n， A， B， C），设置4个参数，用n代表盘片的数量，用A、B、C分别代表起始柱、中间柱和目标柱。然后引导学生借助Python语言编写该函数，利用IF、ELSE分支结构，分为两种情况：当只有1个盘片时，直接从A柱移至B柱;当大于1个盘片时，按上述的移动三部曲进行移动。