汉诺塔调用追踪

Question

我在学习用Python实现汉诺塔的递归算法。在我的程序中，我在不同的地方加了打印语句，以便更好地理解，比如：

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

如果你仔细想想，这一切就很有道理了。

• hanoi(2,A,B,C)
  • hanoi(1,A,C,B)
    • hanoi(0,A,B,C) 这个调用会立刻返回
    • A -> B, n=1
    • hanoi(0,C,A,B) 这个调用也会立刻返回。
  • A -> C, n=2
  • hanoi(1,B,A,C)

等等。换句话说，你感到困惑的那个调用其实是最外层函数中第二个 hanoi 的调用。

Answer 2

如果你再加两个打印语句：

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