河内塔递归调用

Question

1
2   def printMove (to, fr):
3       '''Prints the moves to be executed'''
4       print 'move from ' + str (fr) + ' to ' + str (to)
5   
6   def towers (n, fr, to, sp):
7       if n == 1:            
8     
9       printMove (to, fr)    # 
10      
11      else:
12          towers (n-1, fr, sp, to)  
13                    
14                   
15                 
16          towers (1, fr, to, sp)
17          towers (n - 1, sp, to, fr)
18  
19  towers (3, 'fr', 'to', 'sp')

谁能解释一下为什么这段代码在第 12 行完成递归调用 n 递减到 1，然后再次调用 n = 2 然后移动到第 16 行？我一直在使用 python tutor 并试图理解每个步骤以及算法有效的原因。

Answer 1

首先，题外话：您显示的代码在第 9 行包含一个错误，缩进不合法。

执行从第 19 行开始，它调用 towers(3,...)，继续到第 12 行，调用 towers(2,...)，继续到第 12 行，在那里它调用 towers(1,...)，它会打印一些内容和 returns。当它 returns 时，执行在 towers(2,...) 调用中恢复，并在第 16 行恢复，正如您观察到的那样。

Answer 2

首先，您的代码并不完全正确。这是为您更改的 towers 函数 ->

def towers (n, fr, to, sp):
    if n == 1:            
        printMove (to, fr)
    else:
        towers (n-1, fr, sp, to)
        printMove (to,fr)
        towers (n-1, sp, to, fr)

下面是解释。看图->

通过调用 Movetower(3,a,b,c)，您打算将所有 3 个圆盘从塔 A 移动到塔 B。所以顺序调用是 ->

1. Movetower(3,a,b,c)  // No Move needed
2. Movetower(2,a,c,b)  // No move needed
3. Movetower(1,a,b,c)  // Here is the time to move, move disc1 from a to b
4. Movetower(2,a,c,b)  // Returning to this call again, this is the time to move disc2 from a to c
5. Movetower(1,b,c,a)  // Again the time to move, this time disc1 from b to c
6. Movetower(3,a,b,c)  // Returning to this call again, this is the time to move disc3 from a to b
7. Movetower(2,c,b,a)  // Not the time to move
8. Movetower(1,c,a,b)  // Here is the time to move, move disc1 from c to a
9. Movetower(2,c,b,a)  // Returning to this call again, this is the time to move disc2 from c to b
10.Movetower(1,c,a,b)  // Here is the time to move, move disc1 from a to b

希望对您有所帮助:)

您还可以在这里找到一些很好的解释：Tower of Hanoi: Recursive Algorithm

对于动画：https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

河内塔递归调用

Towers of Hanoi recursive calls

python

algorithm

recursion

towers-of-hanoi