递归这算法还是弄不懂

Question

def move(n, a, b, c):
   if n == 2:
       print a ,'-->', c
       return
   move(n-1,a,c,b)
   print a,'-->',c
   move(n-1,a,b,c)
   print a,'-->',b
   move(n-1,b,a,c)
move(4,'A','B','C')

这个有没有错呢 错误的话该怎样算的呢 求讲解

Answer 1

你只要一步一步的用人脑执行你写的程序，随便设一个n=5之类的，你就知道你写的程序的流程是不太合逻辑的。def move(n, a, b, c):    #目的是从a移动到c    if n == 1:      #如果只有一层，直接移动        print a,'-->',c        return    move(n-1,a,c,b)   #超过一层，将所有动作分解为3步，第1步，将n层中的上面（n-1）层做a到b的移动    move(1,a,b,c)  #第2步，将a上面剩余的一层，做a到c的移动    move(n-1,b,a,c) #第3步，将之前移动的（n-1）层从b移动到c#至于（n-1）这些是怎么移动的，程序会重新嵌套调用，比如n=5，那么先把上4层由a移到b，第五层放c，再把那4层从b移动到c。这是move（5,a,b,c）。那由a移动到b的4层怎么移动呢，这是move(4,a,c,b)这个函数解决的，注意abc顺序。这样递归往下。就好理解了。move(10, 'A', 'B', 'C')

Answer 2

这是汉诺塔问题吧。网上看看思路。递归，要有递归出口，不然是死循环。递归好理解，但是效率低，占空间， 递归是在堆栈中进行的，逐级递归。