Ханойская башня Call Trace

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

Если добавить еще два отпечатка:

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

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)

и др.так далее.Другими словами, озадаченный вызов - это второй вызов hanoi, выполненный в самой внешней функции.