汉诺塔理解递归

对递归的理解一直是展开的方式，拿参数带进去试，但是这种方法实在令我苦恼不已，看知乎上的回答恍然大悟：

image.png
image.png

汉诺塔可以很好的帮助理解递归
举个栗子：

1.三个柱子分别为A、B、C；
2.有3个圆盘，分别编号：1、2、3(从下往上编号)；
3.移动这3个盘子从A搬到C

3层汉诺塔.gif

步骤⬇️：

1. from A move 3号盘子 to C //开始移动除最后一个外其他盘到缓冲区B
2. from A move 2号盘子 to B
3. from C move 3号盘子 to B //除最后一个外其他盘子已经全部放入缓冲区B
4. from A move 1号盘子 to C //最后一个盘移动到C，开始移动其他的盘子从缓冲区B放入到C
5. from B move 3号盘子 to A
6. from B move 2号盘子 to C
7. from A move 3号盘子 to C //除最后一个其他盘子已全部从缓冲区移动到C

从上面的过程+注释可以看出除了最后一个盘子，在最后一个盘子未移动到C之前，其他的盘子都是在从A移动到缓冲区的过程，直到最后一个盘子放入到C，其他的盘子才开始从缓冲区移动到C

因此以上的步骤可以简单概括成

1.把n-1号盘子移动到缓冲区
2.把1号盘子移动到C
3把缓冲区的盘子移动到C

v2-77f7888545bc94292253725fd5033bad_hd.gif

python实现⬇️：

def move(n, f, buffter, t):
    if n == 1:
        print('Move', n, 'from', f, 'to', t)
    else:
        move(n - 1, f, t, buffter)
        move(1, f, buffter, t)
        move(n - 1, buffter, f, t)

对于递归不应该使用展开的方式去理解，没必要从1开始逐个验证，只要证明了“基础条件”，再证明了递推条件，规律会帮我们搞定一切