汉诺塔问题充分体现了递归的简介与深刻

秋雨mac

#1 Created at ... [Delete] [Delete and Lock User]

我刚开始也是把问题想成迭代式或者说是过程式，在下面演算了1，2，3这样简单的例子，想找到移动过程的规则，然后把规则实现为代码，告诉计算机应该怎么做。
最后也是放弃了，参看了回复里面的答案，真的觉得是石破天惊，瞬间觉得递归的深刻与简洁！
其实，这里首先归功于廖老师函数原型声明的很好，mov(n, a, b, c)n交代了问题的规模，a, b, c指明了a上的n个盘子借助b移动到c，这个声明为我们进行递归求解打下了很好的基础。所以代码里面要的很简单：

def mov(n, a, b, c):
    if(n == 1):
        print('%c-->%c', %(a, c))
        #只有一个盘子，可以直接从a移动到c
    else:
        #通过分步减而治之
        mov(n-1, a, c, b)
        #先把上面的n-1个盘子借助c从a移到b
        mov(1, a, b, c)
        #再把a最下面的一个盘子移到c
        mov(n-1, b, a, c)
        #再把b上的n-1个盘子借助a移动到c

KhalilLee1993

#2 Created at ... [Delete] [Delete and Lock User]

def mov(n, a, b, c):
    if(n == 1):
        print('%c-->%c', %(a, c))
        #只有一个盘子，可以直接从a移动到c
    else:
        #通过分步减而治之
        mov(n-1, a, c, b)
        #先把上面的n-1个盘子借助c从a移到b
        mov(1, a, b, c)
        #再把a最下面的一个盘子移到c
        mov(n-1, b, a, c)
        #再把b上的n-1个盘子借助a移动到c

总体思路是这样：第一步就是把A柱子上，除了上最大的（也是最下面的）盘子，借助C移动到B。第二部就是把最大的盘子，从A移到C。

这时候的状态应该是：A柱没盘子，B柱是n-1个盘子，C柱1个最大的盘子。

那么接下来的步骤应该是：把B柱上的n-2个盘子（就是除了B柱最底下的那个第2大的盘子），通过C移到A。然后把B柱剩下的一个第二大的盘子移到C上。这时候的状态就又变成了类似初始状态，A柱子从下到上，从大到小排列，还剩N-2个盘子。B柱子为空。C柱子上面叠了1个最大的和1个第二大的盘子。然后开始新的一轮从A，经由B，再到C。。。

但是请原谅我智商捉急，为什么写出来的代码，看上去比我的思路还要简单？就是把n-1个盘子从A移到B，然后把最大的盘子从A移到C，最后把剩下的盘子从B移到C。。。

为什么啊。。。

你思路第一步就是抽象化的理解，把除开最大的盘子当作一个整体，那么把n-1这个整体借用C移动到B

所以你后面也可以用这种抽象思维理解成，当底部大盘子借B移到C后，n-1这个整体借A移到C

如果按照你后面那种思路想继续执行下去，那么到了 mov(n-1,b,a,c)这一步骤时，可以这么理解：你将mov(n-1, b, a, c)带入之前定义的mov(n,a,b,c)，得到以下内容

def mov(n-1, b, a, c):
#原来是def mov(n, a, b, c):
if(n-1 == 1):
#原来是if(n==1):
    print('%c-->%c', %(b, c))
    #只有一个盘子，可以直接从b移动到c
    #原来是print('%c-->%c',%(a,c))
else:
    #后面就不再重复原来是这些文字了.
    mov(n-2, b, c, a)
    #把上面的n-2个盘子借助c从b移到a
    mov(1, b, a, c)
    #再把b最下面的一个盘子移到c
    mov(n-2, a, b, c)
    #再把a上的n-2个盘子借助b移动到c

后面你如果还想继续你可以选择继续。