2.5 组织数据（1）
给定一些以某种方式组织的数据，现在可能要按另一种方式进行组织。为此必须改变数据的某些特征而不是简单查找。本节讨论Hanoi塔问题。尽管这一经典问题并没有实用价值，但是其解决方案非常适于说明递归的用法，因此下面讲述这一问题。
Hanoi塔
很久以前，在远东的越南城市河内，皇帝的谋士去世了。皇帝要另选谋士。本身极为聪明的皇帝出了一道难题，并宣布解决此题者将获得谋士之位。
皇帝的题目是：设有n个圆盘(皇帝并没有明确有多少圆盘)和3个标杆：A(源)、B(目的)、C(空余)。各个圆盘大小不同，中间有孔，可套在标杆上。圆盘很重，所以只能放在比自身更大的圆盘上。开始时，圆盘都在标杆A上，如图2-16(a)所示。问题要求从标杆A处将圆盘一个个地移到标杆B处。在转移过程中，解题者可使用标杆C，但此时也只能将圆盘放在比自身更大的圆盘上。
谋士是一个令人羡慕的职位，人们争先恐后，踊跃参加。学者和农夫都将方案交给皇帝。许多方案需要上千个步骤，还有很多包含嵌套非常深的循环和控制结构。"我无法理解这些方案。"这位皇帝说，"这个问题一定存在简单的解法。"
简易方法的确存在。一位来自大山的高僧面见皇帝。"我的孩子，这个问题非常容易解决，甚至其本身就存在答案。"皇帝的侍卫甚至想把这位怪人拉走，但皇帝表示要继续听下去。
"如果只有一个圆盘(即n=1)，那就直接把它从标杆A移到标杆B。"至此，很完美。乡村白痴也能做到。"如果存在不止一个圆盘(n>1)，则：
(1) 忽略最底部的圆盘，而求解n-1个圆盘的问题；做一个小小改动，让标杆C为目的杆，而让标杆B为空余杆。(如图2-16(b)所示)
(2) 在完成后，n-1个圆盘将会在标杆C上，而最大的圆盘则留在标杆A上。把圆盘从标杆A处移到标杆B处，就可以解决当n=1时的问题(想一下，乡村白痴也会做)。(如图2-16(c)所示)
(3) 现在的问题是要将n-1个圆盘从标杆C处移至标杆B。换言之，将标杆C看作源杆，将标杆B看作目的杆，将标杆A看作空余杆，来解决问题。"(如图2-16(d)所示)
皇帝沉默了一会，最后不耐烦地说："你到底想不想告诉我们你的方案？"高僧仅微微一笑，就消失了。
很明显，皇帝不懂递归，而实际上，这位高僧的解决方案完全正确。其关键在于：可通过解决3个更小的塔问题(按圆盘数)来解决n个圆盘的塔问题。用towers(count, source, destination, spare)表示将count个圆盘从source杆移到destination杆的问题，将spare杆用作空余杆。注意，即使source杆的圆盘数大于count，这种定义仍有意义，此时可以仅考虑在上面的count个圆盘，而忽略其他圆盘。同样，在开始前，destination杆和spare杆可能就已经存在一些圆盘，这些也可以忽略，只需要将更小的盘放在它们上面。
可重新叙述上面的问题：开始时，标杆A上有n个圆盘，标杆B、C上没有圆盘，求解towers(n, A, B, C)。用下列方式描述高僧的解决方案。
注释：问题的描述
步骤1：在初始状态，所有圆盘都在标杆A上，解决问题
- towers(n - 1, A, C, B)
即忽略底部的最大圆盘，将上面的n-1个圆盘从标杆A移到标杆C，把标杆B看作空余杆。当完成后，最大圆盘仍在标杆A上，而其他圆盘则都在标杆C上。
步骤2：现在，最大圆盘在标杆A上，其他圆盘在标杆C上，解决问题
- towers(1, A, B, C)
即把最大圆盘从标杆A移到标杆B。由于这一圆盘要比标杆C上的已有圆盘大，因此不能使用空余杆。但幸运的是，很明显在这个基例中根本不必使用空余杆。完成后，最大的圆盘在标杆B上，其余的圆盘则在标杆C上。
步骤3：最大圆盘在标杆B上，其余所有圆盘在标杆C上，解决问题
- towers(n - 1, C, B, A)
即把n-1个圆盘从标杆C移到标杆B，将A用作空余杆。注意，目的杆B已经有一个最大圆盘，可将其忽略。完成这一步骤后，实际上已经解决了原始问题：所有圆盘都在标杆B上。
注释：解决方案
问题towers(count, source, destination, spare)解决方案的伪代码如下。
- solveTowers(count, source, destination, spare)
- if (count is 1)
- Move a disk directly from source to destination
- else
- {
- solveTowers(count - 1, source, spare, destination)
- solveTowers(1, source, destination, spare)
- solveTowers(count - 1, spare, destination, source)
- }