我怀着愉悦而激动的心情写下了这篇文章，不仅是因为我独立写出了汉诺塔最具启发性的代码（这么说可能有点狂，好吧），也是因为本人已完全被这种的糅合了自然之美的递归算法所深深震撼，难以想象，如此复杂的问题居然能够被简化翻译成这样简洁而自然的代码。

问题描述

汉诺塔问题是源于印度一个古老传说：古代有一个梵塔，塔内有三个杆 A、B、C 。A 杆上有 64 个盘子，盘子大小不等，大的在下，小的在上。和尚们想把这 64 个盘子从 A 杆移到 C 杆，但每次只能允许移动一个盘子，并且在移动过程中，3 个杆上的盘子始终保持大盘在下，小盘在上。当 64 个盘子全部移到 C 杆，世界就将迎来毁灭。

问题：给出一个参数 n ，请打印将 n 个盘子从 A 杆移动到 C 杆所需要的全部步骤。

思路

当 n=3 时，移动过程如下：

这是最优化的方法。我们知道，递归是指一种通过重复将整个大问题分解为相类似的子问题而解决问题的方法，那么，如果想要使用递归来解决汉诺塔问题，我们就必须先将上面的移动过程分解成最小的单元子过程。

经过思考后不难发现，其实最终是这样一个递归过程：

如果你想把 n 个盘子从 A 移动到 B，那么你需要先把放在上面的 n - 1 个盘子都移动到 B ，然后把最下面的盘子移动到 C ，最后将临时放在 B 上的 n - 1 个盘子都移动到 C ，这就完成了整个过程。
那么现在问题是，如何完成步骤 1 的子过程：把 n - 1 个盘子从 A 移动到 B 。
同步骤 1 类似，你仍然需要先将放在最下面的第 n - 1 个盘子上面所有 n - 2 个盘子从 A 移动到 C ，然后将最下面的盘子移动到 B ，最终将临时放在 C 上的 n - 2 个盘子移动到 B 。
问题又来了，如何完成步骤 2 的子过程：把 n - 2 个盘子从 A 移动到 C 。
继而，如何完成步骤 3 的子过程：把 n - 3 个盘子从 A 移动到 B 。
…

以上就变成了一个嵌套的递归问题，整个大问题将由递归函数逐层拆解。按照上面思路，我们可以初步写出主函数的大概流程：

void hanoi(int n)
{
    move(n - 1, 'a', 'b');//先将上层的n-1个盘子从a移动到b
    move(1, 'a', 'c');    //再将最下面的1个盘子从a移动到c
    move(n - 1, 'b', 'c');//最后将n-1个盘子从b移动到c
}

主函数就是这么简单，剩下的拆解过程交给递归函数 move ：

void move(int n, char from, char to)
{
    if(n == 1)
    {
        std::cout <<"move from " << from << " to " << to << std::endl;//移动盘子
        return;
    }
    char other = 'b' - (from-'b') - (to-'b');
    move(n - 1, from, other); 
    move(1, from, to);
    move(n - 1, other, to);
}

注意到了吗，move 的整体思路和主函数完全相同，只是多了基线条件而已。这个基线条件的含义是：只有当 n = 1，即来到最上层的盘子时，才能移动，因为你不能同时移动多个盘子。

同主函数 hanoi 类似， move 函数的流程是：如果你要把 n 个盘子从 from 移动到 to ，就必须先把上层的 n - 1 个盘子从 from 移动到 other ，然后把最下面的碟子从 from 移动到 to ，最后再把那 n - 1 个盘子从 other 移动到 to 。

第 8 行的代码不太好理解。先假设 a、b、c 三根柱子的代号分别为 -1、0、1 。

如果 from 为 -1 ，to 为 0 ，那么 other 就为 1 ，显然，other 可以这样来得到：1 = - (-1 + 0)

如果 from 为 -1 ，to 为 -1，那么 other 就为 0 ，显然，other 可以这样来得到：0 = - (-1 + 1)

其他同理。

也就是说，当 -1、0、1 中已知两者求第三者时，第三者即等于已知二者的和的相反数。所以第 8 行就是将 a、b、c 各自的 ASCII 码先减去 b 的 ASCII 码，得到 -1、0、1，然后进行如上的求 other 过程。

当 n = 3 时，输出如下：

move from a to c
move from a to b
move from c to b
move from a to c
move from b to a
move from b to c
move from a to c

本文结束。