Tri de fusion récursive et cadres de pile en Python

Question

Le code suivant (pas le mien, juste en train de l'étudier) rebondit (correctement) entre le récursif sur la liste d'origine (c'est-à-dire list_) et la routine de fusion. Le flux des trames de pile (c'est-à-dire, comment et pourquoi elles retournent telles qu'elles sont) n'est pas clair, même en regardant Python Tutor, ce que je raconte plus bas). Une description de la façon dont le code retourne et des questions suivent le programme.

def merge(left, right): 
    if not len(left) or not len(right): 
     return left or right 

    result = [] 
    i, j = 0, 0 
    while (len(result) < len(left) + len(right)): 
     if left[i] < right[j]: 
      result.append(left[i]) 
      i+= 1 
     else: 
      result.append(right[j]) 
      j+= 1 
     if i == len(left) or j == len(right): 
      result.extend(left[i:] or right[j:]) 
      break 

    return result 

def mergesort(list_): 
    if len(list_) < 2: 
     return list_ 

    middle = len(list_)//2 
    left = mergesort(list_[:middle]) 
    right = mergesort(list_[middle:]) 

    return merge(left, right) 


list_ = [7,5,2,1,3] 

print(mergesort(list_)) 

Le premier appel récursif nous avons touché est left (nous voulons trier la moitié gauche de la liste, puis la moitié gauche de la moitié gauche, etc., jusqu'à ce que nous arrivons à une liste de taille et une frapper le cas de base). Cela fonctionne bien. Nous passons de [7,5,2,1,3] à [7,5] à [7] et atteignons le scénario de référence. Jusqu'ici tout va bien. Je m'attends à ce que les cadres de pile commencent à revenir, mais ce n'est pas vraiment ce qui se passe. Je pense qu'il renvoie le 7, mais nous passons ensuite à l'ensemble suivant d'appels récursifs pour right. Le 5 réapparaît. Le 5 est apparu dans le cadre de pile immédiatement avant le 7, donc les choses reviennent dans l'ordre inverse (ce qui est bien). Les nouveaux paramètres séparent le 5 et créent une liste unique, mettant ainsi le cas de base et retournant 5.

Voici où il devient étrange: Le programme passe à l'étape de fusion, qui est correcte. Comment "sait" -il ignorer davantage les récursifs sur right ou left (je lui ai donné une liste entière, dont une grande partie est intacte) et sauter pour fusionner? De plus, comment sait-il revenir à la fonction mergesort à partir de la fusion, sans instruction explicite, et savoir exactement où aller chercher? Quelqu'un peut-il nous éclairer là-dessus? Les textes d'algorithmes traditionnels et la plupart des vidéos n'ont apporté aucune aide, car ils ne traitent pas les cadres de pile.

Answer 1

Je pense que votre confusion a à voir avec le fait de ne pas comprendre que chaque cadre de pile a son propre point d'exécution. Chaque fois qu'une fonction est appelée, l'exécution du cadre est interrompue et un nouveau cadre est créé pour l'appel de fonction. Quand il revient, l'image précédente reprend là où elle s'était arrêtée. Il n'y a pas d'endroit central qui "sait" où le code devrait aller ensuite, chaque niveau gère cela pour lui-même.

Dans le scénario d'exemple que vous avez décrit, l'appel à mergesort[7, 5] d'abord divise les listes vers le haut dans [7] et [5], récursif puis sur chacun d'eux à son tour pour obtenir left et right. Lorsque le second de ces appels récursifs est retourné, il passe à la partie suivante du code, qui est l'appel merge, simplement parce que c'est ce qui vient ensuite dans le code.

Vous pouvez voir la logique tout à fait clairement, ici:

left = mergesort(list_[:middle]) 
right = mergesort(list_[middle:]) 

return merge(left, right) 

Cela vous dit que sur cette course (et chaque course qui ne touche pas le cas de base), il va récursif deux fois, puis merge.