（原创首发）递归典型——汉诺塔问题详解

BngThea

递归问题本身就是容易困扰新手的一个难点，其实很多时候，能不写递归就别写递归
从节能角度来看，效率并不高效，甚至很低
但是以下情况请使用递归：
1 展示才(zhuang)能(bi)
2 其他方法逻辑太过困难，比如汉诺塔问题


汉诺塔问题是初学递归时遇到的较难的问题，详细描述请参考小甲鱼老师的这篇讲解：
http://bbs.fishc.com/thread-79183-1-1.html

本文将重点讲解一个3级的递归实现过程
其实，难就难在理解3级，如果3级理解了，后面的n级只不过是依葫芦画瓢而已

先看代码实现：

def h(n,x,y,z):
    if n == 1:
        print(x,"-->",z)
    else:
        h(n-1,x,z,y)     #将n-1个盘子从x移动到y上
        print(x,"-->",z) #将最底下的最后一个盘子从x移动到z上
        h(n-1,y,x,z)     #将y上的n-1个盘子移动到z上

h(3,'x','y','z')

结果：

x --> z
x --> y
z --> y
x --> z
y --> x
y --> z
x --> z

递归要点： 递归时，一旦进入递归，后续代码暂时挂起，等回归的时候继续执行
汉诺塔难点： 递归过程中实参的不断变换

以 n==3 作为示例，请特别注意实参的变化（为简单起见，print格式随意了）
1  h(3,x,y,z)开始，判断if，此时n==3 if条件不成立， 进入else

2  执行 h(2,x,z,y) #特别注意：此时形参和实参的对应关系是 x-x,y-z,z-y
        2.1 n==2,进入else，执行h(1,x,y,z) #注意实参的匹配
                print x-->z 然后返回
        2.2 print x-->y
        2.3 执行h(1,z,x,y)#注意实参的匹配
                print z-->y 然后返回
        返回到h(3,x,y,z)

3 print x-->z

4 执行 h(2,y,x,z) #特别注意：此时形参和实参的对应关系是 x-y,y-x,z-z
        4.1 n==2,进入else，执行h(1,y,z,x) #注意实参的匹配
                print y-->x 然后返回
        4.2 print y-->z
        4.3 执行h(1,x,y,z)#注意实参的匹配
                print x-->z 然后返回
        返回到h(3,x,y,z)
程序结束

从上面看来，打印结果就是紫色字体的顺序排列

chongchuigu

请指教下第三步骤是执行哪个代码来的   3 print x-->z，返回到h(3,x,y,z)但是3不等于1啊，这个print x-->z是哪里来的？

chongchuigu

看明白了那段代码分了两段执行的是 print(x,"-->",z) #将最底下的最后一个盘子从x移动到z上这个代码。被绕进去了

BngThea

chongchuigu 发表于 2018-6-14 21:28
请指教下第三步骤是执行哪个代码来的   3 print x-->z，返回到h(3,x,y,z)但是3不等于1啊，这个print x-->z ...

n==3的时候，第一部分n==2的递归已经完成后的print语句

myckjx

老司机，赞

myckjx

个别地方有笔误，

1  h(3,x,y,z)开始，判断if n==3不成立， 进入else

这里1写成为3了

BngThea

myckjx 发表于 2018-6-14 22:14
个别地方有笔误，这里1写成为3了

不是笔误，是少了个逗号，意思是判定if
此时n为3，所以不成立

myckjx

还是看不太懂，我自己研究了很久，总结了一些东西不知道对不对，等会发个菜鸟贴子汇报一下

keweel

“2  执行 h(2,x,z,y) #特别注意：此时形参和实参的对应关系是 x-x,y-z,z-y” 形参跟实参对应这些看得出来，但是代码为什么是这样写 看不懂，为什么是h(2,x,z,y) 而不是别的

BngThea

keweel 发表于 2018-6-28 16:53
“2  执行 h(2,x,z,y) #特别注意：此时形参和实参的对应关系是 x-x,y-z,z-y” 形参跟实参对应这些看得出来 ...

因为此时要将x上的盘子移动到y上去，通过z
根据之前的分析，也就是 x, z, y

mhb789456

为什么"2.1 n==2,进入else，执行h(1,x,y,z) #注意实参的匹配"这里不是执行h(1,x,z,y)呢？？？？

BngThea

mhb789456 发表于 2019-4-18 14:57
为什么"2.1 n==2,进入else，执行h(1,x,y,z) #注意实参的匹配"这里不是执行h(1,x,z,y)呢？？？？

是执行h(1,x,z,y)，但是形参对应的变量发生了变化，也就是h(1,x=x,z=y,y=z)，即h(1,x,y,z)

mhb789456

BngThea 发表于 2019-4-19 08:36
是执行h(1,x,z,y)，但是形参对应的变量发生了变化，也就是h(1,x=x,z=y,y=z)，即h(1,x,y,z)

也就是说每次传递参数都是x，y，z吗？

wy1018651314

666666666666