汉诺塔游戏的递归解析

递归

递归就是程序自己调用自己的过程。
本身理解递归的思想比较容易，举一个求阶乘的例子：

def fact(n):
    if n==1:
        return 1
    return n * fact(n - 1)

测试：

>>> fact(1)
1
>>> fact(5)
120

实际上递归程序不可能一直递归循环下去，需要利用其它条件来结束递归循环。这里求阶乘的例子，就是当n==1时就结束递归循环。
这里以fact(5)为例，看程序是如何进行递归运行的

===> fact(5) 
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120

可以看出程序从fact(5)递归到fact(1)结束。从上到下递归至结束，然后从下至上依次计算。

汉诺塔游戏

上面这个递归求阶乘很好理解。但是将递归的思想放到汉诺塔中，就不是那么容易明白了。（关于汉诺塔的文章，其实网上很多了，这里不会很详细解说。）简单说下汉诺塔游戏的规则和玩法：

1. 有三个柱子: a, b, c;
2. a 上有数量为N个的圆盘；
3. 从a柱将数量为N个的圆盘拿到 c 柱上；
4. 一次只能拿一个圆盘，a,b,c 柱都可以利用；
5. 无论在哪根柱子上，都是较大的圆盘永远在较小圆盘下面。

为了方便后面的理解，这里先说明几个字母含义：

N：一个标量，在下文中表示，第N个圆盘，N-1，第N-1个圆盘
n: 代表前n个圆盘， n-1 代表前n-1个圆盘；
a,b,c：分别表示三根柱子；
—>: 箭头表示从...移动到...

玩汉诺塔游戏可以分为三步：

1. 将n-1个圆盘从 a 移到 b上；
2. 将N圆盘从a 移到 c 上；
3. 将n-1 个圆盘，从b 移到c 上。

玩汉诺塔就是不断重复那三步，直到n-1=1。

递归运行图

要将 n 个圆盘从 a 移到 c ，
则先将n-1个从a移到b，然后将N从a移动c，再将n-1从b移到c;
要将n-1个从a移到b，
则先将n-2个从a移到c，然后将N-1从a移动b，再将n-2从c移到b;
要将n-2个从a移到c，
则先将n-3个从a移到b，然后将N-2从a移动c，再将n-3从b移到c;
要将n-3个从a移到b，
则先将n-4个从a移到c，然后将N-3从a移动b，再将n-4从c移到b;
......
在递归到最后一层，n- (n-1)=1, 也就是 a 柱第一个圆盘移向 b 还是 c 取决于N是奇数还是偶数。（代几个数测试下就知道了）
注：要将n-k个从一个柱子移到另一个柱子，需要借助第三个空闲柱子

红色部分递归路径，假设其为递归1号路线，在其下面还有其它递归分支（绿色表示）。等红色的从上往下递归到底后，程序从底下，往上开始计算，遇到绿色则开始递归，等绿色递归完后继续计算上一层的。
程序一开始的递归沿着红色一直递归到最后一层（实际圆盘中最上面的那个）不再进行递归，直接开始搬运圆盘。然后运行最后一层的剩余步骤（黑色，红色），最后一层运行完，
等计算完，红色部分递归1号路线，
程序运行N(a)->c，
然后开始蓝色部分的递归路径（称其递归2号路线），递归2号路线同1号路线一样也有许多递归支路。

为帮助理解，下面是一个路线图，挺丑的，凑合看。。

运行路线图（T_T）

如果单纯值拿红色递归1号路线（不包括其递归支线），其实其和上面的递归阶乘的例子是一样的。但是汉诺塔这个有了许多递归支线，就感觉复杂了许多。同时也可能因为从a->b, a->c, b->c, a->c,a-b...这三个字母混去混来的，脑袋记不住它们关系了，容易犯浑。但是你像图片那样将递归推导列出来就容易明白了。

代码

# Python
def move(n, a, b, c):   #从a将n个圆盘到c
    if n == 1:
        print(f"{a} --> {c}")
    else:
        move(n-1, a, c, b)  #先将n-1圆盘从a移动到b
        print(f"{a} --> {c}") #然后将a移到c
        move(n-1, b, a, c) #再将n-1圆盘从b移动到c
move(4,'a', 'b', 'c')

#include <stdio.h>  
// C
void move(int, char, char, char);

void move(int n, char x, char y, char z)
{
        if (n == 1)
        {
                printf("%c --> %c\n", x, z);
        }
        else
        {
                move(n-1, x, z, y);
                printf("%c --> %c\n", x, z);
                move(n-1, y, x, z);
        }
}

int main()
{
        int n;
        scanf("%d", &n);
        move(n, 'a', 'b', 'c');
        return 0;
}

参考：

递归函数

原文: 汉诺塔游戏的递归解析

相关文章：

二叉树与汉诺塔