024递归：汉诺塔的代码疑问，求大神指引

kernelkernel

关于小甲鱼第24讲中，游戏汉若塔的代码，怎么都想不明白究竟原理是怎样的。只能求助于各位大神，帮我解疑惑！小弟菜
先看看正确的代码：

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 )
     
    
n = int(3)
hanoi ( n , '左' , '中', '右' )

输出的结果：
左  到  右
左  →  中
右  到  中
左  →  右
中  到  左
中  →  右
左  到  右


这个是正确的代码和输出结果。 当中我无法理解，整个递归的顺序步骤，程序是如何执行的，也就是每一行的输出结果应该对应哪一行代码

有两位热心网友进行初步解答，可惜小弟才疏学浅无法理解透彻。然后对代码进行更改看能否更好地理解程序的步骤。经过改动，以下的输出结果是按照我的思路去输出的结果。没错，结果显然是错误的。但是，我的思路就是这样的，为什么正确的结果中，会有右到左呢？明明程序都没写过这样的结果。   

以下是我更改过后的错误输出结果程序，但是思路却是按照我对程序的理解的顺序执行的。
代码如下：

def hanoi(n , x , y , z): #建立函数
    if n == 1 :     #判断是否等于1，等于1就是trun（真）
        print ( x , ' 到 ' , z )   #输出结果
    else:     #不等于1的时候执行调用自身直到输出上面的结果
        hanoi ( n - 1 , ' 我是左边', '我是右边' , '我是中间' )   #重新定义参数，同时次减一，避免死循环；
        print ( x , ' → ' , z )   #输出结果，但是我不明白这个结果为什么会被执行
        hanoi ( n - 1 , '我系中间的' , '我系左边的' , '我系右边的' ) #当输出的是三，那么第一次执行的话，这里会是多少减一呢？（n=？减一）
     
    
n = int(3)   #假设是三而已，如果是四，五，六呢？
hanoi ( n , '左' , '中', '右' )   #这个是得到具体赋值后调用hanoi函数，同时赋予了后三个具体的参数。

------------------------------------------------------------
结果输出如下：

我是左边  到  我是中间
我是左边  →  我是中间
我系中间的  到  我系右边的
左  →  右
我是左边  到  我是中间
我系中间的  →  我系右边的
我系中间的  到  我系右边的


-----------------------------------------------------------------

希望有高手能详细说明，整个程序的工作流程及步骤。

lumber2388779

hanoi (3 , '左' , '中', '右' ) - >
        else: hanoi ( 2 , '左' ,'右', '中') ->
                else: hanoi ( 1 , '左' , '中', '右')->
                        if: print ( 左, ' 到 ' , 右) ->
                print ( 左, ' → ' , 中)->
                hanoi ( 1  , '右', '左', '中')->
                        if:print ( 右, ' 到 ' , 中)->
        print( 左, ' → ' , 右)->
        hanoi (2 , '中' ,'左', '右')->
                else:hanoi ( 1  , '中', '右', '左')->
                        if: print ( 中, ' 到 ' , 左)->
                print( 中, ' → ' , 右)->
                hanoi ( 1  , '左', '中', '右')->
                        if: print ( 左, ' 到 ' , 右)

大概就是这个过程，你看下能看懂不

99592938

我最初想通这个也是想了很久，你可以假设将n个盘子看作一个打包好的整体，从x到z只需要把包挪一次。
然后对这个包分析，将包分为两个包：最底下的一个，上面的n-1个。然后挪到位就需要三步：
n-1：x→y    1: x→z   n-1:y→z
然后n-1可以继续分两个包。。。。知道n=1时就分不开了，递归也就到头了。
以下是百度的一段代码，将每个盘子作了标记，更容易理解：

B=[] #设置操作过程列表
def move(n, a, b, c):
        if n==1:
                buzhou=a+str(n)+'-->'+c+str(n) #一个圆盘需要从A到C操作步骤
                B.append(buzhou) #向列表中添加操作步骤
        else:
                move(n-1,a,c,b) #将A柱的n-1个盘移到B柱
                buzhou=a+str(n)+'-->'+c+str(n) #将A柱的n-1个盘移到C柱操作步骤
                B.append(buzhou) #向列表中添加操作步骤
                move(n-1,b,a,c) #将过渡柱子B上n-1个圆盘B移动到目标柱子C
move(6,'A','B','C') #2**64-1，64次太大，这里用6个盘子
print(str(len(B)),B) #计算6个盘子的步骤数及操作过程

kernelkernel

lumber2388779 发表于 2017-4-4 23:16
大概就是这个过程，你看下能看懂不

你这样太模糊了。可能是我说的不清楚。
当我输入数值3时，为什么输出左到右？    根据代码判断，if n == 1；这个条件肯定不通过就会执行else，但是else的下一跳代码是hanoi(n-1,x,z,y) ,怎么说都是按照这个条件重新进入hanoi自身进入继续执行if n ==1,进行判断。

这个中间的输出结果该如何将递归进行分开循环，理解呢？  我是这个意思。

kernelkernel

99592938 发表于 2017-4-5 11:51
我最初想通这个也是想了很久，你可以假设将n个盘子看作一个打包好的整体，从x到z只需要把包挪一次。
然后 ...

你这样太模糊了。可能是我说的不清楚。
当我输入数值3时，为什么输出左到右？    根据代码判断，if n == 1；这个条件肯定不通过就会执行else，但是else的下一跳代码是hanoi(n-1,x,z,y) ,怎么说都是按照这个条件重新进入hanoi自身进入继续执行if n ==1,进行判断。

这个中间的输出结果该如何将递归进行分开循环，理解呢？  我是这个意思。

kernelkernel

为什么输出的第三个结果回事右到中，  代码中哪里说明输出结果会是右到中？    我把程序的步骤一步步走下来，无法走。。。不知道其原理。就像我输入3，if的条件就一定不会执行了。直接走else，执行hanoi(n-1,x,z,y)，之后程序会不会继续执行下去呢？ 应该不会，因为下面的是输出结果是→符号不是到，而实际输出结果是输出，‘到’。  就是说程序在else，hanoi(n-1,x,z,y)这里把数据减到2-1为止，再让if==1成立输出左到右的。 但到了第二个输出结果，左到中，是不是就在else的第一个递归中，满足了hanoi(n-1,x,z,y)达到n == 1的条件令到左→中成立呢？ 明显hanoi（n-1,x,z,y）中的z,和y调换了位置，令到源自身的函数z变成了第一个递归中的Y，所以输出左→右。 这些都可以这样说明，但是到了右到中就无法理解了。

99592938

kernelkernel 发表于 2017-4-6 22:29
你这样太模糊了。可能是我说的不清楚。
当我输入数值3时，为什么输出左到右？    根据代码判断，if n == ...

做了个图，你看看，其实你用“到”和“→”分这个，是比较容易区分的

kernelkernel

lumber2388779 发表于 2017-4-4 23:16
大概就是这个过程，你看下能看懂不

第六行和第七行代码如何理解？ 为什么右这个参数会放在第一个参数了。

kernelkernel

99592938 发表于 2017-4-7 00:10
做了个图，你看看，其实你用“到”和“→”分这个，是比较容易区分的

不是很清晰。 帖子我已经重新编辑过了。你可以看看。我想知道的是步骤。还有为什么正确结果会有右到中

99592938

kernelkernel 发表于 2017-4-7 10:41
不是很清晰。 帖子我已经重新编辑过了。你可以看看。我想知道的是步骤。还有为什么正确结果会有右到中

计算机就照着顺序执行的每一步骤啊，递归递归，没递到底就不归，然后至于右到中，你拿三个饼子自己摆一下就知道了。我有点明白你不懂在什么地方了，你把左中右看得很局限，可以这样想想：把汉诺塔的三个支点放在等边三角形的角上，三个支点不要带方向属性，如果还不明白，我真帮不了你

99592938

kernelkernel 发表于 2017-4-7 10:41
不是很清晰。 帖子我已经重新编辑过了。你可以看看。我想知道的是步骤。还有为什么正确结果会有右到中

大兄弟，你一楼的第二个代码写的详细，但确实错了，要多想，跳出左中右的概念，因为计算机执行函数用的是形参，不是n,x,y,z这几个绝对字符，而是四个参数的在位置上的字符

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 )
     
    
n = int(3)
hanoi ( n , '左' , '中', '右' )

第7行，y与x对调，就是在n-1执行的时候，汉诺塔的“柱子”换了啊

kernelkernel

99592938 发表于 2017-4-7 11:04
大兄弟，你一楼的第二个代码写的详细，但确实错了，要多想，跳出左中右的概念，因为计算机执行函数用的是 ...

嗯嗯，我知道你想表达的意思。我肯定明白形参啊。 不然我不会在第一部份的代码中更改函数中的形参。 问题是我卡在了第一部分的代码里面。   按照我目前的对这个代码的理解就是，无论你输入什么数值，最终应该打印输出的就是print（）里面的内容，而两个print（）的内容，怎样都无法理解会有右到中这个输出结果。我说得清楚吗？