图解方式解析汉诺塔递归算法的教学实践

周鑫

摘要：该文对递归算法的实质进行了探讨。以汉诺塔问题为例，提出一种图解的方式，直观地展示了递归算法的具体执行过程，有助于初学者对递归思想的深入理解。

关键词：递归；图解；汉诺塔

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2014）07-1444-02

递归是一种有效的算法设计方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。递归是高中信息学奥赛必须掌握的基本算法思想，但在实际教学中却发现，初学者对程序执行的具体过程和参数传递过程难以理解，无法领会递归的实质。为此，笔者根据自己多年的教学实践，以汉诺塔——递归的典型例题为例，提出一种图解的方式，展开递归算法的具体执行过程。

1 汉诺塔问题描述

汉诺塔是一个经典的数学问题，其具体描述如下：有三根相邻的柱子，标号为A，B，C，A 柱上从下到上按金字塔状叠放着n 个不同大小的圆盘，现在把所有盘子借助于A，B，C 三个柱子一个一个移动到C柱上，并且每次移动在同一根柱子上都不能出现大盘在小盘上方的现象。根据问题描述得到以下规则：

1）圆盘必须一个一个的移动；

2）大的圆盘必须在小圆盘的下方或单一圆盘；

3）满足规则2）的序列可以出现在A，B，C 任意一根塔上。传说布拉马圣

2 汉诺塔问题的算法分析

汉诺塔问题中盘子的移动过程虽然繁琐，却有规律性可循。要想将A柱上的N个盘子移动至C柱，可以通过以下三个步骤实现：1）以C柱为过渡柱，从A柱将1至N- 1号盘移至B柱。2）将A柱中剩下的第N号盘移至C柱。3） 以A柱为过渡柱，从B柱将1至N- 1号盘移至C柱。这明显是一个递归的过程，不断深入，不断细小化，最终，将到达仅有一个盘的情形，这时， 递归也就终止了，问题也得到了解决。我们看到，整个递归过程可分解为两个问题，即最小子问题和汉诺塔问题。其中，步骤2是递归的终止条件，是一个能直接求解的最小子问题，只需移动一个盘子就完成任务。步骤1、3均是n-1階的汉诺塔问题，不同阶的区别在于各柱的作用不同。这样，原问题被转换为与原问题性质相同、规模变小的子问题。即：将Hanoi（N，A，B，C） 转化为Hanoi（N- 1，A，C，B） 与Hanoi（N- 1，B，A，C） 。其中Hanoi（）中的参数分别表示需移动的盘子数、起始柱、过渡柱与目标柱。

4 结束语

本文提出的图解方式，较为直观地描述了递归执行的具体过程，详细描述了如何利用它来解释递归的实现过程。清晰明了地展现了递归过程中参数传递，局部变量的变化情况及过程调用和过程返回的执行情况，是一种科学有效的说明递归问题的方法，有助于初学者深入理解递归的思想。经过前后两届学生的教学实践验证，教学满意度提高，对理解递归的效果显著。

参考文献：

[1] 谭浩强. C 程序设计[M].北京： 清华大学出版社，2011.

[2] 严蔚敏.吴伟民.数据结构（ C 语言版）. 北京清华大学出版社，2011.

[3] 王挺，周会平. C+ + 程序设计[M].北京： 清华大学出版社， 2005.

[4] 白会波， 高瑞平. 汉诺塔问题的算法分析及C 语言演示程序的实现[J].电脑知识与技术， 2010（18）.