递归
递归就是程序自己调用自己的过程。
本身理解递归的思想比较容易，举一个求阶乘的例子：
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)结束。从上到下递归至结束，然后从下至上依次计算。
汉诺塔游戏
上面这个递归求阶乘很好理解。但是将递归的思想放到汉诺塔中，就不是那么容易明白了。（关于汉诺塔的文章，其实网上很多了，这里不会很详细解说。）简单说下汉诺塔游戏的规则和玩法：
- 有三个柱子: a, b, c;
- a 上有数量为N个的圆盘；
- 从a柱将数量为N个的圆盘拿到 c 柱上；
- 一次只能拿一个圆盘，a,b,c 柱都可以利用；
- 无论在哪根柱子上，都是较大的圆盘永远在较小圆盘下面。
为了方便后面的理解，这里先说明几个字母含义：
N：一个标量，在下文中表示，第N个圆盘，N-1，第N-1个圆盘
n: 代表前n个圆盘， n-1 代表前n-1个圆盘；
a,b,c：分别表示三根柱子；
—>: 箭头表示从...移动到...
玩汉诺塔游戏可以分为三步：
- 将n-1个圆盘从 a 移到 b上；
- 将N圆盘从a 移到 c 上；
- 将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...这三个字母混去混来的，脑袋记不住它们关系了，容易犯浑。但是你像图片那样将递归推导列出来就容易明白了。
代码
# 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;
}
参考：
原文: 汉诺塔游戏的递归解析
相关文章：
