摘要：递归算法是计算机专业数据结构与程序设计课程中的重难点，汉诺塔问题是一个使用递归算法实现的经典问题。现有教材往往侧重于汉诺塔问题的分析及程序实现，缺少对递归程序复杂执行过程的解析。教学实践中将汉诺塔问题求解的递归算法与二叉树的中序遍历结合起来，以图解的方式直观展示整个递归函数执行过程，有助于学生真正理解递归思想，也为教师对汉诺塔递归算法的教学提供新思路。
关键词：二叉树;递归;汉诺塔;中序遍历;图解
中图分类号：TP301 文献标识码：A
文章编号：1009-3044（2020）31-0149-03
Abstract： Recursive algorithm is an important and difficult point in computer specialty courses of Data Structure and Program Design. The Tower of Hanoi problem is a classical problem which is solved through recursive algorithm. The existing teaching materials tend to focus on analysis and program realization of the Tower of Hanoi problem， lacking in analysis of the complex execution process of the recursive program. We can combine the Tower of Hanoi recursive algorithm of problem solving and binary tree Inorder traversal in educational practice. The entire recursive function execution process is displayed directly in a graphical way， which helps students understand the idea of recursion， and provides a new idea for the teaching of the Tower of Hanoi recursive algorithm.
Keywords： binary tree; recursive; the Tower of Hanoi; Inorder traversal; diagram
1 引言
程序調用自身的编程技巧称为递归。递归作为一种算法在程序设计语言中广泛应用。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归程序代码精简、功能强大。在计算机专业的数据结构、C++语言程序设计、算法分析等课程中，递归会经常遇到，现今流行的高级程序设计语言也都支持函数的递归调用。所以，教师对递归概念的讲解是否清楚，会直接影响学员今后使用递归解决实际问题的编程能力。现有教材中涉及递归概念时都会引用经典的汉诺塔问题，但经研究发现此类教材对汉诺塔问题的描述侧重于汉诺塔金片搬运过程的分析及编程实现，而对程序的复杂递归调用执行过程缺乏解析，不便于学员理解。为此，在教学实践中，将汉诺塔递归算法与二叉树中序遍历结合起来，以二叉树中序遍历图解来模拟汉诺塔递归程序的复杂调用过程。
2 汉诺塔问题
2.1原始问题
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。[1]
2.2抽象成数学问题
将原始问题抽象成数学问题：有三根针A、B、C，初始时A针上有64个圆盘，圆盘大小不一，小的在上，大的在下;B、C针上无圆盘（如图1所示），要求把A针上64个圆盘移到C针上。移动时遵循3条规则：（1）只给一个中间过渡用针（称针B）;（2）每次只能移动一个圆盘;（3）任何时候，都要保持小盘在上，大盘在下。[2]试编程求出移动步骤与步数。
2.3递归求解思路
设圆盘总个数为N，从上至下给圆盘编号为1～N。当N=1时，直接将编号为1的圆盘从A针移动到C针;当N=2时，先将编号为1的圆盘从A针移动到B针，再将编号为2的圆盘从A针移动到C针，最后将编号为1的圆盘从B针移动到C针;当N>2时，可以将A针上编号1～N-1的圆盘看作一个整体，整个搬运过程与N=2时类似，也分为三个步骤：
（1） 借助C针将A针上这N-1个圆盘移动到B针上;
（2） 将A针上最大的圆盘直接移动到C针上;
（3） 借助A针将B针上N-1个圆盘移动到C针上。
同样，对于这N-1个圆盘的移动方法递归上述搬运过程。
2.4 汉诺塔问题的C语言实现代码
#include "stdio.h"
int i=1;//全局变量，记录移动步数
void hanoi（int n，char a，char b ，char c）;
void main（）
{
int n;
char a='A'，b='B'，c='C';
printf（"请输入圆盘的个数：＼n"）;
scanf（"%d"，&n）;
printf（"圆盘总数为%d时移动情况如下：＼n"，n）;
hanoi（n，a，b，c）;
}
void hanoi（int n，char a，char b，char c）
{ //算法里（1）～（4）是为了说明执行过程加入的标号
（1） if（n==0） return;
（2） hanoi（n-1，a，c，b）;
（3） printf（"第%d步：将%d号圆盘%c-->%c＼n"，i++，n，a，c）;
（4） hanoi（n-1，b，a，c）;
}
程序运行时结果如图2所示：
3 二叉树中序遍历模拟汉诺塔递归程序执行过程
3.1二叉树的中序遍历
所谓遍历就是按照一定的顺序依次访问树中的每一个结点，而且每个结点只被访问一次。[3]二叉树中序遍历的递归算法定义如下：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树;
⑵访问根结点;
⑶遍历右子树。
按中序遍历图3所示的二叉树，结点信息输出顺序为：D-H-B-I-E-A-J-F-K-C-G。
3.2 二叉树的中序算法实现
用二叉链表作为存储结构，中序遍历算法可描述为：
void InOrder（BinTree T）
{ //算法里（1）～（4）是为了说明执行过程加入的标号
（1） if（T==NULL） return;//如果是空结点，返回
（2） InOrder（T->lchild）;//遍历左子树
（3） printf（"%c"，T->data）; // 访问结点内容
（4） InOrder（T->rchild）;//遍历右子树
}
3.3 汉诺塔递归算法与二叉树中序遍历算法的共同点
将hanoi函数与InOrder函数进行对比，会发现除代码表达的问题含义不同外，其代码结构完全一致。两个函数中语句（1）都是递归结束语句;语句（2）、（4） 都为递归到下一层的函数调用;语句（3）都是一条输出信息语句。据此共同点，可以将汉诺递归执行过程转换成二叉树的中序遍历过程。教学实践中启发学生将hanoi函数中的语句（2）理解为访问左子树，语句（3）理解为输出结点信息，语句（4）理解为访问右子树。
3.4图解模拟汉诺塔程序的递归执行过程
教学实践中取汉诺塔圆盘总数为4进行模拟，以主函数中hanoi（4，A，B，C）为根结点，为作图方便省略函数名，同时注意参数的传递变化规律。
整个递归程序执行过程见图4中的虚线路径，程序从根结点开始，不断沿左子树遍历到结点、结点、结点，当到达叶子结点时，此时参数n=1，再往下层递归时由于n=0，直接返回，程序执行时只是输出结点信息：“第1步，将1号圆盘A-->B”，然后返回到结点代表的函数体语句（3），执行结点的信息输出，再遍历结点的右子树，输出叶子结点的信息…… 按二叉树的中序遍历会依次输出结点至的信息，输出结果与图2中程序实际执行结果完全一致。
通过对图4的观察，能得到汉诺塔问题的求解步数，编号为4的圆盘搬运了2（4-4）=1次，编号为3的圆盘搬运了2（4-3）=2次，编号为2的结点搬运了2（4-2）=4次，编号为1的结点搬运了2（4-1）=8次。推广到圆盘总数为N时，编号为i的圆盘搬运次数为2（n-i）次，总搬运次数为20+21+22+ ……+2N-1=2N-1次。
4 结束语
通过二叉树中序遍历将汉诺塔复杂的递归调用过程图形化，使学生对递归复杂的调用、返回有了感性的认识，加深了对递归思想的深入理解。以安徽广播电视大学2019春、2019秋两届计算机本科专业学员为教学对象，分别采用传统方式与二叉树中序遍历图解法讲解汉诺塔递归算法，课后完成相同的练习，得出采用新方法教学，学员正确率提高近30%，教学效果显著提升。
參考文献：
[1] 严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2007：54-55.
[2] 张海峰.“递归”与“汉诺塔”的直观教学演示[J].中原工学院学报，2004，15（3）：35-39.
[3] 吴鹤龄.程序设计基础[M].北京：中央广播电视大学出版社，2004：148.
0
