рекурсивные узлы

Question

В своем уроке я пытаюсь понять, как читать приведенную ниже функцию с именем printBackward. Как получается, что когда я печатаю printBackward(node1), и у меня выводится 3,2,1, это то, что он должен делать. Я просто не понимаю, почему это так. Посмотрите ниже, как я интерпретирую это, и, пожалуйста, учите меня, где я увидел это неправильно ...

 class Node:
    def __init__(self, cargo = None, next = None): # optional parameters. cargo and the link(next) are set to None.
        self.cargo = cargo
        self.next = next

    def __str__(self):
        return str(self.cargo)


node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3

# Exercise
def printList(node):

    print "[",
    while node:
        print node,
        node = node.next
        if node != None:
            print ",",
    print "]",
    print


def printBackward(list):
    if list == None: return
    head = list      
    tail = list.next 
    printBackward(tail) 
    print head,

Итак, скажем ... printBackward(node1) сначала, if list следует игнорировать, поскольку узел1 содержит ссылку на узел2, поэтому мы переходим к head = list, который является узлом1. tail = list.next который я вижу как node1.next = node2, так что tail = node2. Затем мы получаем printBackward(tail), который является node2. В этот момент, что происходит? Мы делаем это снова и снова? Я вижу, что это происходит до узла 3, который в этот момент вернет None. Когда мы доберемся до print head, ??? Мы делаем рекурсивный вызов еще до того, как доберемся до print head,? Пожалуйста, научите меня, как я пытаюсь понять примеры, которые даны мне в моем уроке. Спасибо!

Answer 1

Рекурсия сама вызывает функцию. Итак, давайте посмотрим порядок вызова функции printBackward.

printBackward(node1)
 |
 +-> printBackward(node2)
      |
      +-> printBackward(node3)
           |
           +-> printBackward(None)
          print node3
     print node2
print node1

Как видите, printBackward1 вызывается с аргументом node1. Перед печатью node1 он передает поток управления printBackward (node2). И когда printBackward (node2) завершается, он печатает node1.

Answer 2

Вы правы во всем, что происходит, когда вызывается printBackward(node3).То, что происходит, - каждый раз, когда вы получаете рекурсивный вызов printBackward(), вы углубляетесь в стек вызовов.Финальный print фактически не вызывается до тех пор, пока рекурсия не перестанет вызывать printBackward(), а затем раскручивается.Когда он возвращается каждый раз, то вызывается print, поэтому вы получаете обратный порядок.print происходит во время раскрутки стека вызовов.Когда вы получаете node3, tail становится None, и следующий вызов printBackwards() - это то, что сразу возвращается, и начинается печать.скрывают несколько встроенных имен Python (list и next).