[已解决]汉诺塔递归问题

fan1993423

from pysnooper.pysnooper import snoop
@snoop()
def hanoi(n,x,y,z):
    if n==1:print(x,'->',z)
    else:
        hanoi(n-1,x,z,y)
        print(x,'->',z)
        hanoi(n-1,y,x,z)
hanoi(4,'X','Y','Z')

这是汉诺塔递归，我想问一下，这里起始n=4,然后执行hanoi(n-1,x,z,y)，慢慢从4到3到2，再到1的时候执行if语句。接着程序又是怎么走的。对递归还是理解很深，希望大佬指点一下。

最佳答案

月排行榜 / 总排行榜

Stubborn

2020-1-16 20:50:13

跳转到最佳答案楼层

Stubborn

zltzlt

当盘子数大于 1 时：

1. 用递归操作，将除了最下面的盘子外的所有盘子从 X 柱移到 Z 柱（用递归操作）；
2. 将最下面的盘子从 X 柱移到 Y 柱；
3. 将 Z 柱上的所有盘子移到 Y 柱（用递归操作）。

当盘子数等于 1 时，将盘子从 X 柱移到 Z 柱（一步操作）。

fan1993423

zltzlt 发表于 2020-1-16 21:02
当盘子数大于 1 时：

1. 用递归操作，将除了最下面的盘子外的所有盘子从 X 柱移到 Z 柱（用递归操作）； ...

我知道，思路我明白，但是就是不懂程序是怎么运作的，这种有两个递归的我脑袋有点糊

塔利班

想象实际操作就行了

fan1993423

塔利班 发表于 2020-1-16 21:38
想象实际操作就行了

写一下这个程序具体是怎么走的吧

塔利班

fan1993423 发表于 2020-1-16 21:46
写一下这个程序具体是怎么走的吧

n->1 ，换柱子，完了

fan1993423

塔利班 发表于 2020-1-16 21:47
n->1 ，换柱子，完了

我知道思路，假设从n=4开始，每一步是执行哪一个函数，我感觉在相互调用，我用pysnooper看了下，n=4,3,2,1,1,2,1,1,3,2,1,1,2,1,1 我不知道中间是怎么执行函数的，哪个又在调用哪个函数

Stubborn

参考流程，对照汉诺塔把，简单流程画一画

fan1993423

Stubborn 发表于 2020-1-16 22:12
参考流程，对照汉诺塔把，简单流程画一画

这个单层的我懂，就是不懂这种双层的是怎么调用
比方 n+fun(n-1)
        print(n)
        n+fun(n-1)
就是在这个函数中有两个递归，是怎么个流程

Stubborn

fan1993423 发表于 2020-1-16 22:25
这个单层的我懂，就是不懂这种双层的是怎么调用
比方 n+fun(n-1)
        print(n)

http://pythontutor.makerbean.com/visualize.html#mode=edit    去这个运行可视化，看下运行步骤

fan1993423

Stubborn 发表于 2020-1-16 22:40
一样一样的啊，比如上图中，return n + fun(3)  出结果了，那么这个递归就算结束。进行下面的步骤。

...

那我想问下，在执行后面那个递归的时候，程序又会不会倒过来执行前面按个递归，虽然前面那个递归有出口了，但是在执行后面那个递归的时候，前面那个递归包含在程序的下面

Stubborn

fan1993423 发表于 2020-1-16 22:46
那我想问下，在执行后面那个递归的时候，程序又会不会倒过来执行前面按个递归，虽然前面那个递归有出口了 ...

运行到函数，就需要得到函数的返回（None  或者有其他值）程序才能运行下去。一步一步走

可以去bilibili 看下并归排序，就是这种例子

belongbosco

期待一个满意答案

烟肖雨晨

您好，很荣幸可以帮助您解决问题！（其实我本人以前也对这块很晕，所以我跟你很有共鸣）

【以下是我写这个程序的注释】
==========================================
def hanoi(n,x,y,z):
    'n是hanoi塔层数，x是第一座塔名，y是第二座塔名，z是第三座塔名'#函数的文档
   
    if n == 1:#递归终止条件
        print(x,"->",z)#如果只有一个盘子，则直接将其从x柱移至z柱

    else:
        hanoi(n-1,x,z,y)#将n-1个盘子从x柱移到y柱
                       #因为上面的递归终止条件，所以实现将n-1个盘子从x柱移至y柱需要将x与x，y与z一一对应
        
        print(x,"->",z) #将最底下的盘子从x柱移到z柱
        
        hanoi(n-1,y,x,z)#将n-1个盘子从y柱移到z柱
                       #因为上面的递归终止条件，所以实现将n-1个盘子从y柱移至z柱需要将y与x，z与z一一对应

n=int(input("请输入hanoi塔层数："))
hanoi(n,'x','y','z')

=====================================
我不知道你是对哪里还有疑惑，我当时是没搞懂它为什么要这样变换参数来传参数。
=======================================
x -> y
x -> z
y -> z
x -> y
z -> x
z -> y
x -> y
x -> z
y -> z
y -> x
z -> x
y -> z
x -> y
x -> z
y -> z
================================
这个是它的运行路径，我认为，可能你不要挑太复杂的来模拟，你可以用n=1，或n=2来进行模拟。相信我，试一下，再将小甲鱼提到的要点整合总结一下，应该会有所收获。还有不清楚的可以再问，谢谢！

fan1993423

Stubborn 发表于 2020-1-16 20:50

我就是要这个路程图，我在下来理解下

fan1993423

烟肖雨晨 发表于 2020-1-18 17:31
您好，很荣幸可以帮助您解决问题！（其实我本人以前也对这块很晕，所以我跟你很有共鸣）

【以下是我写这 ...

也谢谢你，我知道结果，就是这种二路递归到底是个怎么运行路径我不太清楚

Stubborn

fan1993423 发表于 2020-1-19 13:15
我就是要这个路程图，我在下来理解下

遇到函数，必先要有结果

MCDULLtotto

我不动为什么换一下xyz的顺序，他就换了