nœuds récursifs

Question

J'essaie de comprendre dans ma leçon comment lire la fonction ci-dessous appelée printBackward. Comment est-ce que lorsque je tape printBackward(node1) et ma sortie est 3,2,1 ce qui est ce que c'est supposé faire. Je ne comprends tout simplement pas pourquoi. Voir ci-dessous comment je l'interprète et vous me école où je l'ai vu mal ...

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, 

Alors disons que ... printBackward(node1) au début, if list doit être ignorée car node1 contient une référence à node2 donc nous allons à head = list qui est node1. tail = list.next que je vois comme node1.next = node2 donc tail = node2. Ensuite, nous arrivons à printBackward(tail) qui est node2. À ce moment-là, que se passe-t-il? Est-ce qu'on refait tout ça? Je vois cela aller jusqu'à node3 qui à ce moment-là retournera None. Quand arrivons-nous à print head, ??? Nous faisons un appel récursif avant même d'arriver au print head,? S'il vous plaît, éduquez-moi en essayant de comprendre les exemples qui me sont donnés dans ma leçon. Merci!

Answer 1

Vous avez raison de tout ce qui se passe avant printBackward(node3). Ce qui se passe est chaque fois que vous obtenez l'appel printBackward() récursif, vous allez plus loin dans la pile d'appels. Le dernier print ne sera pas appelé jusqu'à ce que la récursivité arrête d'appeler printBackward(), puis se déroule. Comme il revient à chaque fois, alors le print est appelé, c'est pourquoi vous obtenez l'ordre inverse. Les print se produisent pendant le déroulement de la pile d'appels. Lorsque vous arrivez à node3, tail devient None, et que le prochain appel au printBackwards() est ce qui revient tout de suite, et l'impression commence.

printBackward(node1) 
    printBackward(node2) 
     printBackward(node3) 
      printBackward(None) 
     print node3 
    print node2 
print node1 

également une petite note, vous êtes shadowing quelques noms de python intégrés (list et next).

Answer 2

La récursivité est la fonction d'appel elle-même. Voyons donc l'ordre d'appel de la fonction printBackward.

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

Comme vous pouvez le voir, printBackward1 est appelée avec node1 comme argument. Avant d'imprimer node1, il donne le flux de contrôle à printBackward (node2). Et lorsque printBackward (node2) est terminé, il imprime node1.