河内电话塔追踪

我正在学习python河内递归实现塔。在我prgram我给在不同的点打印多知道一点像河内电话塔追踪

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

我不可能理解一个 - > C后打印。在调用n = 0之后src = A inm = B dest = C之后，我知道函数会被返回。那里的活动函数是n = 1 src = A inm = C dest = B。会发生什么？

请解释跟踪

来源

2012-01-21 user567879

如果您添加两个打印：

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

来源

2012-01-21 18:58:56

如果您仔细考虑，这是非常有意义的。

河内（2，A，B，C）
- 河内（1，A，C，B）
  - 河内（0，A，B，C）立即返回
  - 甲 - > B，n = 1
  - hanoi（0，C，A，B）立即返回。
- A - > C，n = 2的
- 河内（1，B，A，C）

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

来源

2012-01-21 18:52:22 katrielalex

河内电话塔追踪

回答

相关问题