栈与递归的实现 -- 汉诺塔

第三章第三节 栈与递归的实现
栈大家都熟悉，先进后出，栈顶在下，栈底在上，添加元素会栈底位置增加
栈的特性决定了它在处理一些特殊情况的时候很占优势，例如，括号匹配，这节重点 - 递归

汉诺塔相信大家都很熟悉，规则很简单，目的就是将x上的三个饼插到z上，大饼不能在小饼上面，一次只能移动一个饼。如图：

灵魂画师之汉诺塔

二话不说就是一个算法

void hanoi (int n, char x, char y, char z) {
    //函数意义：将塔座x上按直径从小到大且自上而下编号为1-n 的n个圆盘按规则搬至z，y做辅助
    if(n == 1) {
        move(x, 1, z);
    } else {
        hanoi(n-1, x, z, y);
        move(x, n, z);
        hanoi(n-1, y, x, z);
    }
}

汉诺塔的递归其实挺简单的，但是它就是实实在在的对于递归核心思想的考验 - 如何设计递归？
我认为递归的核心在于1、如何将问题一层层剥开；2、剥开到最后是一个最简单的操作。

我对于汉诺塔的递归思路是这样的:

• 汉诺塔目的是将整个塔转移，而这个塔每少一层，就是对于问题的一层简化，直至最终只剩下一层，这个时候，汉诺塔就成为了最简单的一次操作了。所以先定下最基本操作，把“最上的某1层”从“起点”挪到“目的地”。
• 然后来看递归体如何设计，这个就是需要了解汉诺塔的规则了，汉诺塔不能同时挪动多个，而且只能把小的放在大的上面，而我们有一个辅助塔座可以使用。这时如何一层层剥开这个问题的答案已经出来了，就是我们每次转移一层的时候，将这一层跟其上的所有层分离开，如此完成问题的一层层剥离。so，递归体就是，借助另外的那个塔座作辅助，将要挪动的那一层上面的所有层先转移到辅助塔座，然后转移最下层到目的塔座，然后再将辅助塔座上的那几层转移到目的塔座。

emmm，大致就是这样了，希望我说清楚了，如果没说清的话，溜了溜了~