ハノイの塔コールトレース

Question

私はハノイの再帰的実装の塔をPythonで研究していました。私はどのように理解couldntの私は

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

件まで理解することができ

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 

：私の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') 

のようにそれをよりよく知るために異なるポイントで印刷しました - > Cがこの後に印刷されます。 n = 0の呼び出しの後にsrc = A inm = B dest = C、私は関数が返されることを知っています。そこでは、アクティブな関数はn = 1です。src = A inm = C dest = B何が起こりますか？

トレースを説明してください。

Answer 1

あなたが2枚の以上のプリント追加する場合：

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 

：

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

を次にあなたが行に2つのリターンがあったことがわかります

Answer 2

これは慎重に考えると理にかなっています。

• ハノイ（2、A、B、C）
  • ハノイ（1、A、C、B）
    • ハノイ（0、A、B、C）A
    • 直ちに返します - > B、n = 1
    • ハノイ（0、C、A、B）はすぐに戻ります。
  • A - > C、N = 2
  • ハノイ（1、B、A、C）

エトセトラ。言い換えれば、あなたが困惑しているコールは、最も外側の機能で行われた第2のhanoiコールです。