递归

递归就是程序自己调用自己的过程。

本身理解递归的思想比较容易，举一个求阶乘的例子：

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号路线一样也有许多递归支路。

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

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

代码

# Pythondef move(n, a, b, c):    if n == 1:        print(f"{a} --> {c}")    else:        move(n-1, a, c, b)        print(f"{a} --> {c}")        move(n-1, b, a, c)move(4,'a', 'b', 'c')

#include 
    
       // Cvoid 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;}
    

参考：

原文: