python - 汉诺塔调用追踪

Question

我正在研究Python中的汉诺塔递归实现。在我的程序中，我在不同的点给出了 print 以便更好地了解它，例如

def hanoi(n, src, inm, dest):
    print "n=",n,"src=",src,"inm=",inm,"dest=",dest
    if n == 0:
        return
    hanoi(n-1, src, dest, inm)
    print src, '->', dest
    print n 
    hanoi(n-1, inm, src, dest)

hanoi(2,'A','B','C')

答案打印如下:

n= 2 src= A inm= B dest= C
n= 1 src= A inm= C dest= B
n= 0 src= A inm= B dest= C
A -> B
1
n= 0 src= C inm= A dest= B
A -> C
2
n= 1 src= B inm= A dest= C
n= 0 src= B inm= C dest= A
B -> C
1
n= 0 src= A inm= B dest= C

我最多能听懂

   1
    n= 0 src= C inm= A dest= B

我无法理解此后如何打印 A -> C 。在使用 n= 0 src= A inm= B dest= C 进行调用后，我知道函数将被返回。活跃函数是 n= 1 src= A inm= C dest= B。这会发生什么？

请解释一下踪迹

Answer 1

如果您再添加两个打印件:

print "r1"   # before first return
print "r2"   # at the end of the function, before second, implicit return

然后你会看到连续有两个返回:

n= 2 src= A inm= B dest= C
n= 1 src= A inm= C dest= B
n= 0 src= A inm= B dest= C
r1
A -> B
1
n= 0 src= C inm= A dest= B
r1
r2
A -> C
2
n= 1 src= B inm= A dest= C
n= 0 src= B inm= C dest= A
r1
B -> C
1
n= 0 src= A inm= B dest= C
r1
r2
r2