Рекурсивная функция, окончательная заявка на печать

Question

Я самообучающийся Python, используя как думать, как компьютерный ученый. Я изучаю «Узлы и связанные списки». Эта рекурсивная функция меня путает. Чтобы быть ясным, код работает нормально. Я спрашиваю, как возможно, что выполняется заключительная строка кода внизу (print list,)?

Мой вопрос относительно этой рекурсивной функции:

def print_backward (list): 
    if list == None: return #shouldn't the code terminate when this is satisfied? 
    print_backward(list.next) 
    print list, #seems like the function would terminate before this line 
       #ever gets called 

Может кто-нибудь объяснить мне, когда эта последняя строка print head, выполняется? Читая этот код, я бы подумал, что после вычисления каждого узла мы вернемся к вершине функции, а затем, когда мы дойдем до третьего и последнего узлов, завершающий оператор if list == None: return будет удовлетворен, и тогда код выйдет из цикла, никогда достигая утверждения печати в самом низу. Ясно, что этого не происходит, поскольку вызывается оператор печати.

Я спрашиваю, потому что я чувствую, что не знаю, не понимаю, как работает код! Если кто-то может объяснить, как код попадает в этот окончательный оператор печати (и он туда добирается), я бы очень признателен. Надеюсь, я не нарушу правила, спросив об этом. Благодаря!

BTW Я печатаю связанный, список, груз [1,2,3]. Распечатайте его назад, поэтому [3,2,1] Ниже приведен код для большего контекста.

---

class Node: 
    def __init__(self, cargo = None, next = None): 
     self.cargo = cargo 
     self.next = next 

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

def print_list(node): 
    while node: 
     print node, 
     node = node.next 
    print 


def print_backward (list): 
    if list == None: return 
    print_backward(list.next) 
    print list, 

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

node1.next = node2 
node2.next = node3 
node3.next = None 

print_backward(node1) 

Выход:

==== RESTART: /Users/Desktop/Programming Career/Untitled.py ====

3 2 1 

Answer 1

Рекурсия не означает прыжки в верхнюю часть функции; это означает вызов той же функции в пределах функция.

Я думаю, что более простой пример делает его более очевидным:

def count(number): 
    if number <= 0: return 
    count(number-1) 
    print(number) 

Когда мы называем count(3), функция будет печатать цифры от 1 до 3. Почему? Потому что это то, что происходит:

1. count(3) называется.
2. number - 3, который не ниже или равен нулю, поэтому мы не делаем return.
3. Мы называем count(3-1):
   1. count(2) называется.
   2. number is 2, который не ниже или равен нулю, поэтому мы не делаем return.
   3. Мы называем count(2-1):
      1. count(1) называется.
      2. number 1, который не ниже или равен нулю, поэтому мы не делаем return.
      3. Мы называем count(1-1):
         1. count(0) называется.
         2. number равно 0, что равно нулю, поэтому мы return до предыдущего уровня.
      4. Мы print 1.
   4. Мы print 2.
4. Мы print 3.

Answer 2

Разберем через то, что код делает узел узлом

1. print_backward вызывается с node1
2. есть node1 == None нет? Нет, так мы продолжаем
3. Зададим head = node1
4. Зададим tail = node1.next же, как tail = node2
5. Мы называем print_backward(tail) же, как print_backward(node2)
   1. print_backward вызывается с node2
   2. не node2 == None ни? Нет, так мы продолжаем
   3. Зададим head = node2
   4. Зададим tail = node2.next же, как tail = node3
   5. Мы называем print_backward(tail) же, как print_backward(node3)
      1. print_backward вызывается с node3
      2. не node3 == None ни?Нет, так мы продолжаем
      3. Зададим head = node3
      4. Зададим tail = node3.next же, как tail = None
      5. Мы называем print_backward(tail) же, как print_backward(None)
         1. print_backward вызывается с None
         2. не None == None ни? Да, так мы возвращаем
      6. print head, называется, так же как print node3, (печать "3")
   6. print head, называется, так же как print node2, (печать "2")
6. print head, является называемый так же, как print node1, (печать «1»)

Общий выход: «3 2 1 "!