（原创首发）递归典型——汉诺塔问题详解
本帖最后由 BngThea 于 2018-6-14 22:29 编辑递归问题本身就是容易困扰新手的一个难点，其实很多时候，能不写递归就别写递归
从节能角度来看，效率并不高效，甚至很低
但是以下情况请使用递归：
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格式随意了）
1h(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)
程序结束
从上面看来，打印结果就是紫色字体的顺序排列 请指教下第三步骤是执行哪个代码来的 3 print x-->z，返回到h(3,x,y,z)但是3不等于1啊，这个print x-->z是哪里来的？ 看明白了那段代码分了两段执行的是 print(x,"-->",z) #将最底下的最后一个盘子从x移动到z上这个代码。被绕进去了 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语句 老司机，赞{:5_106:} 个别地方有笔误，1h(3,x,y,z)开始，判断if n==3不成立， 进入else这里1写成为3了 myckjx 发表于 2018-6-14 22:14
个别地方有笔误，这里1写成为3了
不是笔误，是少了个逗号，意思是判定if
此时n为3，所以不成立 还是看不太懂，我自己研究了很久，总结了一些东西不知道对不对，等会发个菜鸟贴子汇报一下{:5_108:} “2执行 h(2,x,z,y) #特别注意：此时形参和实参的对应关系是 x-x,y-z,z-y” 形参跟实参对应这些看得出来，但是代码为什么是这样写 看不懂，为什么是h(2,x,z,y) 而不是别的 keweel 发表于 2018-6-28 16:53
“2执行 h(2,x,z,y) #特别注意：此时形参和实参的对应关系是 x-x,y-z,z-y” 形参跟实参对应这些看得出来 ...
因为此时要将x上的盘子移动到y上去，通过z
根据之前的分析，也就是 x, z, y 为什么"2.1 n==2,进入else，执行h(1,x,y,z) #注意实参的匹配"这里不是执行h(1,x,z,y)呢？？？？ 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) 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吗？ 666666666666
页:
[1]