Envisagez la conversion de Python récursif en non récursif

introduction

Si les fonctions récursives sont pratiques, elles présentent également des inconvénients. Pour cette raison, les fonctions récursives ont longtemps été converties en fonctions non récursives. La conversion elle-même a été faite, mais elle était aléatoire et je ne pensais pas théoriquement pourquoi elle pouvait être convertie. Je voulais penser théoriquement au processus de conversion, mais je n'ai pas pu saisir l'occasion. Pendant ce temps, l'article sur les fonctions récursives était à la hausse, j'ai donc commencé à écrire des articles. (Ça fait longtemps que je l'ai laissé seul) Un autre facteur est que j'écrivais un autre programme et que j'avais réalisé l'importance de l'empilement.

Cependant, cela ne nie pas l'utilité des fonctions récursives. J'adore les fonctions récursives.

Lecteur supposé

Le langage de programmation peut être n'importe quoi, je vais donc utiliser Python. Je n'expliquerai pas l'algorithme lui-même utilisé pour créer le programme récursif. Par conséquent, il est destiné à ceux qui comprennent Python et comprennent (examinent) les algorithmes.

Appeler la pile et la pile

La pile qui contrôle l'exécution du programme est appelée pile d'appels (Call Statck). Il est également appelé Execution Stack, Control Stack, Function Stack, etc. Dans cet article, nous nous unifierons avec la pile d'appels. De plus, la pile en tant que structure de données est simplement appelée pile.

Pourquoi les fonctions récursives peuvent être évitées

Les fonctions récursives utilisent la pile d'appels en appelant la fonction. Il existe une limite supérieure à la capacité qui peut être stockée dans la pile d'appels. La capacité peut être modifiée en modifiant les paramètres du compilateur, etc., mais elle est toujours limitée. (Je l'ai touché récemment, donc je ne sais pas à quel point il est flexible.) Si la capacité de la pile d'appels est dépassée, un débordement de pile se produit et l'exécution du programme s'arrête. En principe, les fonctions récursives ont tendance à consommer une grande quantité de pile d'appels et à provoquer un débordement de pile. Cela dépend des paramètres, mais d'après mon expérience, qui n'est pas si nombreux, il est facile d'utiliser la pile d'appels et de provoquer un débordement de pile. (C'est peut-être à cause de votre programme d'excréments) Par conséquent, il a tendance à être évité.

D'autre part, l'espace de tas utilisé par la pile est relativement plus flexible que la pile d'appels. (Je pense que cela dépend aussi des paramètres et du programme à créer) Par conséquent, nous allons passer à l'utilisation de la pile.

Récemment, il y a des compilateurs qui ont une fonction appelée optimisation de la réception de fin qui convertit la réception de fin en une structure de boucle. Ça va mieux sans trop s'inquiéter. Cela devient plus pratique.

Politique de conversion

Dans cet article, je pense que c'est une méthode de conversion typique, mais j'aimerais envisager de faire d'une fonction récursive une fonction non récursive à l'aide d'une pile. Ceci est une image de la commutation de l'utilisation de la pile d'appels à l'utilisation de la pile.

Sol

Prenons d'abord un simple revêtement de sol à titre d'exemple.

Version récursive hiérarchique

La mise en œuvre de la hiérarchie utilisant récursive est la suivante.

def  factorialR(n) :
    if n == 0 :
        return 1
    return n *  factorialR(n-1)

Mouvement hiérarchique de la pile d'appels récursifs

Illustrons à quoi ressemble la pile d'appels lorsque cette fonction est exécutée avec n = 5. Ce n'est pas une opération stricte mais un mouvement d'image. Lorsque la fonction est exécutée, elle pousse d'abord l'appel lui-même factorialR (5) vers la pile d'appels. «factorialR (5)» est converti en «5 * factorialR (4)» lorsqu'il est exécuté.

Appelez ensuite factorialR (4) et poussez-le dans la pile d'appels. «factorialR (4)» est converti en «4 * factorialR (3)» lorsqu'il est exécuté.

Par la suite, cela fonctionne de la même manière.

L'appel récursif s'est poursuivi jusqu'à n = 0.

Si n = 0, 1 est renvoyé.

Quand factorialR (0) est exécuté et 1 est retourné, la pile d'appels est abaissée de un. Ensuite, il retourne au moment où n = 1 est appelé, «1 * factorialR (0)» est résolu et «1 * 1 = 1» est renvoyé.

De même, le retour du résultat de l'exécution précédente réduit la pile d'appels de un. Il revient au point où n = 2 est appelé et «2 * factorialR (1)» est résolu et «2 * 1 = 2» est renvoyé. Par la suite, cela fonctionne de la même manière.

Enfin, 5 * factorialR (4) = 5 * 24 = 120 et 120 est renvoyé.

Dans la version récursive, l'appel est effectué de manière récursive, de sorte que l'appel est empilé sur la pile d'appels. Je veux conserver la structure de la fonction et ne pas utiliser la pile d'appels. La fonction ci-dessus nécessitait le résultat du calcul au milieu et l'argument utilisé pour l'appel de fonction suivant pour calculer la puissance. Par conséquent, essayons de placer le résultat du calcul au milieu dans une variable et la valeur utilisée pour le prochain appel de fonction sur la pile. Dans le cas de «5 * f (4)», 5 est mis sur la variable et 4 sur la pile. Sur la base de cette idée, j'aimerais faire une version non récursive.

Version non récursive

Encore une fois, illustrons le comportement de la pile lorsque n = 5. Lorsque la fonction démarre, elle pousse d'abord 5 sur la pile. Définissez également la variable Résultat qui enregistre le résultat du calcul au milieu sur 1.

L'étape suivante consiste à faire apparaître la pile et à récupérer la valeur 5. Multipliez ensuite Result par la valeur extraite. Enfin, poussez la valeur 4 de «5-1 = 4» dans la pile.

L'étape suivante consiste à faire sauter la pile pour récupérer la valeur 4. Multipliez ensuite Result par la valeur extraite. Enfin, poussez la valeur 3 de «5-1 = 3» dans la pile.

Par la suite, cela fonctionne de la même manière.

Pop la valeur 0 puis multiplier le résultat par 1. Si 0, il n'y a pas de valeur suivante à pousser sur la pile.

Maintenant que la pile est partie, la valeur de résultat de 120 est recherchée comme réponse à la puissance de n = 5. Je pense que vous pouvez trouver le sens d'utiliser la pile parce que le revêtement de sol est simple. Cependant, je fais cela pour généraliser la conversion. Faisons-en une fonction basée sur cela. Pour être honnête, serait-ce comme suit?

def factorialL(n):
    stack = [n]
    result = 1
    current = 0
    while len(stack) > 0:
        current = stack.pop()
        if current <= 0:
            current = 1
        else :
            stack.append(current - 1)
        result *= current
    return result

Hiérarchie version non récursive partie 2

Considérez une implémentation qui reproduit le comportement de la version récursive de la pile d'appels sur la pile. Déplaçons la pile comme suit.

Lorsque n = 0, c'est "0! = 1", donc 1 est fixe.

Puis pop le 1 confirmé et cassez une pile. Enregistrez ce sauté 1 comme résultat.

Ensuite, faites apparaître la valeur supérieure 1 et divisez une pile. Calculez «1 * 1» en utilisant le 1 enregistré précédemment et le 1 que vous venez de faire apparaître, et enregistrez «1» comme résultat. Cela confirme la valeur de n = 1. Par la suite, il sera exécuté de la même manière.

Pop la valeur supérieure 2 et multipliez-la par la valeur de résultat 1 pour obtenir le résultat 2 dans le résultat.

Pop la valeur supérieure 3 et multipliez-la par la valeur de résultat 2 pour obtenir le résultat 6 dans le résultat.

Pop la valeur Top 4 et multipliez-la par la valeur de résultat 6 pour obtenir le résultat 24 dans le résultat.

Pop la valeur Top 5 et multipliez-la par la valeur de résultat 24 pour obtenir le résultat 120 dans le résultat.

Maintenant que la pile est partie, la valeur de résultat de 120 est recherchée comme réponse à la puissance de n = 5.

Dans ce cas, serait-ce comme suit?

def factorialL(n):
    stack = []
    for i in range(n, 0, -1) :
        stack.append(i)
    result = 1
    for i in range(len(stack)) :
        top = stack.pop()
        result *= top
    return result

Simplification des versions non récursives de la hiérarchie

Une implémentation légèrement plus claire ressemble à ceci:

def factorial1(n):
    result = 1
    for i in range(1, n + 1) :
        result *= i
    return result

from functools import reduce
def factorial2(n):
    return reduce(lambda a, b: a * b, range(1, n + 1), 1)

Séquence de Fibonacci

Ensuite, je voudrais prendre la séquence de Fibonacci comme exemple.

Version récursive de la séquence de Fibonacci

Une implémentation typique utilisant la récurrence de séquence de Fibonacci ressemblerait à ceci: La grande différence par rapport au revêtement de sol est que vous vous appelez deux fois en une seule fois.

def fibonacciR(n) :
    if n == 0 or n == 1 :
        return n
    return fibonacciR(n - 2) + fibonacciR(n - 1)

Comportement de la pile d'appels récursifs de séquence de Fibonacci

Illustrons l'état de la pile d'appels lorsque n = 5 comme dans le cas du revêtement de sol. Lorsque la fonction est exécutée, fibonacciR (5) est d'abord poussé vers la pile d'appels. Ensuite, il est converti en «fibonacciR (3) + fibonacciR (4)».

Puis fibonacciR (3) est appelé et poussé dans la pile d'appels. Une fois exécuté, il sera converti en fibonacciR (1) + fibonacciR (2).

Ensuite, fibonacciR (1) est appelé et poussé dans la pile d'appels. fibonacciR (1) renvoie 1 lorsqu'il est exécuté. Cela résout partiellement «fibonacciR (1) + fibonacciR (2)» en appelant «fibonacciR (3)» pour devenir «1 + fibonacciR (2)».

Pour résoudre fibonacciR (2), il est appelé et poussé dans la pile d'appels. Une fois exécuté, il sera converti en fibonacciR (0) + fibonacciR (1).

fibonacciR (0) est appelé et poussé dans la pile d'appels. fibonacciR (0) renvoie 0 lorsqu'il est exécuté. Cela résout partiellement «fibonacciR (0) + fibonacciR (1)» en appelant «fibonacciR (2)» pour devenir «0 + fibonacciR (1)».

De même, fibonacciR (1) est appelé et poussé dans la pile d'appels. fibonacciR (1) renvoie 1 lorsqu'il est exécuté. Cela résout «0 + fibonacciR (1)» lors de l'appel de «fibonacciR (2)» en «0 + 1 = 1».

«1 + fibonacciR (1)» lors de l'appel de «fibonacciR (3)» est résolu en «1 + 1 = 2».

Une partie de «fibonacciR (3) + fibonacciR (4)» en appelant «fibonacciR (5)» est résolue pour devenir «2 + fibonacciR (4)».

Cela fonctionne de la même manière ci-dessous.

Cela fonctionne comme ci-dessus et renvoie la valeur 5 lorsque n = 5. Je l'ai écrit pendant longtemps, mais le comportement de la pile d'appels est comme ça. Cela seul est difficile à comprendre, donc je voudrais utiliser une bissectrice pour représenter le mouvement de cette pile d'appels.

Séquence de Fibonacci version récursive du demi-arbre

Exprimé comme un arbre à deux branches, il se présente comme suit.

graph TB;
    0[5]---1[3]
    0---2[4]
    1---3[1]
    1---4[2]
    4---5[0]
    4---6[1]
    2---7[2]
    2---8[3]
    7---9[0]
    7---10[1]
    8---11[1]
    8---12[2]
    12---13[0]
    12---14[1]

Vous pouvez voir que la profondeur de la pile d'appels correspond à la profondeur du demi-arbre. Vous pouvez également voir que l'ordre dans lequel les valeurs sont résolues correspond à l'ordre de recherche de la recherche de priorité en profondeur de l'arbre bifurqué. La recherche de priorité en profondeur des arbres bifurqués est souvent décrite comme étant mise en œuvre à l'aide de piles. Ici, il est implémenté en utilisant la pile d'appels.

Ensuite, je voudrais faire une version non récursive.

Version non récursive de la séquence de Fibonacci

La version récursive de la séquence de Fibonacci est également une fonction simple, et il n'y a pas de résultat de calcul au milieu. Donc, ce qu'il faut mettre sur la pile est de mettre les arguments passés à la fonction sur la pile.

Illustrons la situation d'empilement lorsque n = 5 comme précédemment. Lorsqu'il commence à s'exécuter, il pousse le premier argument donné 5 sur la pile.

L'étape suivante consiste à ouvrir la pile et à en récupérer 5. 5 ne peut pas déterminer la valeur à partir de la formule graduelle de la séquence de Fibonacci. Au lieu de cela, nous demanderons "n-2" et "n-1". En d'autres termes, poussez respectivement «5-2 = 3» et «5-1 = 4» dans la pile. Je vais d'abord pousser du plus grand nombre.

L'étape suivante consiste à ouvrir la pile et à en récupérer 3. 3 ne peut pas déterminer la valeur, alors appuyez sur 1 et 2 respectivement à la place.

L'étape suivante consiste à ouvrir la pile et à récupérer le 1. 1 peut être déterminé comme une valeur, alors enregistrez-le comme résultat.

L'étape suivante consiste à ouvrir la pile et à en récupérer 2. 2 ne peut pas déterminer la valeur, alors appuyez sur 0, 1 respectivement.

L'étape suivante consiste à faire apparaître la pile et à récupérer les 0. Puisque 0 peut être déterminé comme valeur, ajoutez-le à Result et enregistrez-le.

L'étape suivante consiste à ouvrir la pile et à récupérer le 1. Puisque 1 peut être déterminé comme valeur, ajoutez-le au résultat et enregistrez-le.

Par la suite, cela fonctionne de la même manière.

Cela fonctionne comme ci-dessus et renvoie également la valeur 5 lorsque n = 5. Je voudrais à nouveau mettre en œuvre cela honnêtement.

def fibonacciL(n) :
  result = 0
  current = 0
  stack = [n]
  while len(stack) > 0 :
    current = stack.pop()
    if current == 1 or current == 0 :
      result += current
    else :
      stack.append(current-1)
      stack.append(current-2)
  return result

J'ai opté pour une implémentation similaire à celle du floor riding. (Bien que j'essaie d'avoir une implémentation similaire)

Simplification non récursive de la séquence de Fibonacci

Si vous voulez uniquement la réponse sans connaître la pile, vous pouvez également effectuer les opérations suivantes. Dans le cas d'une pile, il a été calculé à partir de celui avec le plus grand coefficient de l'expression graduelle, tel que «n-> n-1-> n-2-> ...-> 0». Celui-ci est calculé à partir de celui avec le coefficient le plus petit, tel que «0-> 1-> ...-> n».

def fibonacciL2(n):
  if n == 0:
    return 0
  x, y = 0, 1
  for _ in range(n - 1):
    x, y = y, x + y
  return y

Tri rapide

Ensuite, envisagez un tri rapide.

Version récursive de tri rapide

J'ai essayé d'implémenter le tri rapide de manière récursive comme suit. J'essaye d'obtenir des valeurs en double. Je pense qu'il y a quelques différences par rapport à la mise en œuvre typique, mais je pense que c'est un tri rapide. J'ai inclus print () pour montrer le processus de tri. Nous définissons et utilisons également des fonctions auxiliaires à cette fin. ʻIsSorted () `détermine s'il est trié.

def isSorted(lt):
  b = lt[0]
  for x in lt:
    if b > x:
      return False
    b = x
  return True

def getListIndeces(lt, s=0):
  if len(lt) == 0:
    return "><"
  maxLen = len(str(max(lt)))
  text = reduce(lambda x, y: x + y, [f"{i+s:{maxLen}}, " for i, x in enumerate(lt)], ">")
  return f"{text[:-2]}<"


def listToFormatedString(lt):
  if len(lt) == 0:
    return "[]"
  maxLen = len(str(max(lt)))
  text = reduce(lambda x, y: x + y, [f"{x:{maxLen}}, " for x in lt], "[")
  return f"{text[:-2]}]"

def getPivot(lt, l, r):
  return lt[l + int((r - l) / 2)]

def quickSort(lt):
  _quickSort(lt, 0, len(lt) - 1)

def _quickSort(lt, l, r):
  if l >= r:
    print(f"   {getListIndeces(lt[l:r+1], s=l)}, l: {l}, r: {r}\nr: {listToFormatedString(lt[l:r+1])}")
    return
  i = l
  j = r
  p = getPivot(lt, l, r)
  print(f"   {getListIndeces(lt[l:r+1], s=l)}, l: {l}, r: {r}, p: {p}\ns: {listToFormatedString(lt[l:r+1])}")
  while i < j:
    while lt[i] < p:
      i += 1
    while lt[j] > p:
      j -= 1
    if i < j:
      if lt[i] == lt[j]:
        j -= 1
      else:
        lt[i], lt[j] = lt[j], lt[i]
    print(f"p: {listToFormatedString(lt[l:r+1])}, {i}: {lt[j]}, {j}: {lt[i]}")
  _quickSort(lt, l, i - 1)
  _quickSort(lt, j + 1, r)

Donnez [7, 2, 1, 4, 6, 0, 8, 5, 9, 3] comme argument et exécutez-le.

lt = [7, 2, 1, 4, 6, 0, 8, 5, 9, 3]
quickSort(lt)
print(lt, isSorted(lt))

Ensuite, le résultat d'exécution suivant sera affiché.

   >0, 1, 2, 3, 4, 5, 6, 7, 8, 9<, l: 0, r: 9, p: 6
s: [7, 2, 1, 4, 6, 0, 8, 5, 9, 3]
p: [3, 2, 1, 4, 6, 0, 8, 5, 9, 7], 0: 7, 9: 3
p: [3, 2, 1, 4, 5, 0, 8, 6, 9, 7], 4: 6, 7: 5
p: [3, 2, 1, 4, 5, 0, 6, 8, 9, 7], 6: 8, 7: 6
p: [3, 2, 1, 4, 5, 0, 6, 8, 9, 7], 6: 6, 6: 6
   >0, 1, 2, 3, 4, 5<, l: 0, r: 5, p: 1
s: [3, 2, 1, 4, 5, 0]
p: [0, 2, 1, 4, 5, 3], 0: 3, 5: 0
p: [0, 1, 2, 4, 5, 3], 1: 2, 2: 1
p: [0, 1, 2, 4, 5, 3], 1: 1, 1: 1
r: >0<, l: 0, r: 0
r: [0]
   >2, 3, 4, 5<, l: 2, r: 5, p: 4
s: [2, 4, 5, 3]
p: [2, 3, 5, 4], 3: 4, 5: 3
p: [2, 3, 4, 5], 4: 5, 5: 4
p: [2, 3, 4, 5], 4: 4, 4: 4
   >2, 3<, l: 2, r: 3, p: 2
s: [2, 3]
p: [2, 3], 2: 2, 2: 2
r: ><, l: 2, r: 1
r: []
r: >3<, l: 3, r: 3
r: [3]
r: >5<, l: 5, r: 5
r: [5]
   >7, 8, 9<, l: 7, r: 9, p: 9
s: [8, 9, 7]
p: [8, 7, 9], 8: 9, 9: 7
p: [8, 7, 9], 9: 9, 9: 9
   >7, 8<, l: 7, r: 8, p: 8
s: [8, 7]
p: [7, 8], 7: 8, 8: 7
p: [7, 8], 8: 8, 8: 8
r: >7<, l: 7, r: 7
r: [7]
r: ><, l: 9, r: 8
r: []
r: ><, l: 10, r: 9
r: []
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] True

Comportement de la pile d'appels récursifs de tri rapide

Le tri rapide illustre également le mouvement de la pile d'appels. Tout d'abord, il est poussé vers la pile d'appels comme f (lt).

6 est initialement sélectionné comme pivot, les valeurs inférieures à 6 sont déplacées vers l'avant de la liste et les valeurs supérieures à 6 sont déplacées vers l'arrière de la liste. Comme résultat du tri, puisque l'indice de limite est 6, quickSort () est exécuté à lt [0: 6] et lt [7:10] respectivement. La valeur de l'indice de frontière est le pivot. S'il y a des valeurs en double, la valeur sélectionnée comme pivot peut être dans la liste triée. L'indice des limites est trié et la position est fixe. L'élément dont la position est fixe sera affiché comme «Résultat».

La pile d'appels est ensuite poussée avec f (lt [0: 6]) pour l'exécution.

Ici, 1 est choisi comme pivot, les valeurs inférieures à 1 étant fractionnées vers l'avant et les valeurs supérieures à 1 étant fractionnées vers l'arrière. L'index du délimiteur est 1, et quickSort () est exécuté sur lt [0: 1] ʻet lt [2: 6] `, respectivement.

F (lt [0: 1]) est poussé vers la pile d'appels.

lt [0: 1] a une longueur de 1, donc il est positionné et sorti de la pile d'appels.

La pile d'appels retourne, puis la plage de lt [2: 6] est triée. Ici, 4 est choisi comme pivot et est divisé en une plage de valeurs inférieures à 4 et de valeurs supérieures à 4. L'index du délimiteur est 4, et quickSort () est exécuté sur lt [2: 4] ʻet lt [5: 6] `, respectivement. Établissez la position de «lt [4]».

F (lt [2: 4]) est poussé vers la pile d'appels.

2 est choisi comme pivot et est divisé en moins de 2 et plus de 2. quickSort () est exécuté à lt [2: 2] et lt [3: 4], respectivement, séparés par un index de délimitation de 2. «lt [2]» est confirmé.

Les deux lt [2: 2] et lt [3: 4] sont exécutés, mais la position est fixe car la longueur de la plage est de 1 ou moins. f (lt [2: 2]) est poussé et sauté parce qu'il a une longueur de 0. f (lt [3: 4]) est exécuté, la position de lt [3] est fixée, et elle est sautée.

La pile d'appels retourne, puis la plage de lt [5: 6] est triée. Puisque lt [5: 6] a également une plage de 1, la position est fixe et sautée. La première moitié de la liste est maintenant triée et confirmée. La seconde moitié est traitée de la même manière.

9 est choisi comme pivot et est divisé en «lt [7: 9]» et «lt [9: 9]». «lt [9]» est confirmé.

f (lt [7: 9]) est poussé.

8 est choisi comme pivot et est divisé en «lt [7: 8]» et «lt [8: 8]». «lt [8]» est confirmé.

f (lt [7: 8]) est poussé.

La position de «lt [7]» est fixe.

Les deux lt [8: 8] et lt [9: 9] ont une longueur de 0, donc ils se terminent sans rien faire et le processus se termine.

Vous pouvez voir qu'il est maintenant similaire au comportement de la pile d'appels dans la séquence de Fibonacci.

Version non récursive de tri rapide

Le tri rapide sera également converti en non récursif. Le processus d'empilement sur la pile d'appels est empilé sur la pile de la même manière que la manière conventionnelle de penser. Dans le cas d'un tri rapide, la plage qui doit être triée ensuite est empilée sur la pile. La mise en œuvre ressemble à ceci: Je pensais que ce serait pénible, mais maintenant c'est presque la même chose que la version rétrospective.

def quickSortL(lt):
  length = len(lt)
  stack = [(0, length - 1)]
  while len(stack) > 0:
    l, r = stack.pop()
    if l >= r:
      continue
    i = l
    j = r
    p = getPivot(lt, l, r)
    while i < j:
      while lt[i] < p:
        i += 1
      while lt[j] > p:
        j -= 1
      if i < j:
        if lt[i] == lt[j]:
          j -= 1
        else:
          lt[i], lt[j] = lt[j], lt[i]
    stack.append((j + 1, r))
    stack.append((l, i - 1))

Recherche en 2 minutes

À ce stade, c'est un slapstick, mais j'aimerais envisager une recherche de deux minutes.

Version récursive de recherche de 2 minutes

Tout d'abord, c'est une version récursive, mais je l'ai implémentée comme suit. Cela suppose que vous transmettez une liste triée avec des valeurs uniques. Vous pouvez utiliser ʻuniqueSorted () pour créer une liste qui remplit les conditions. Cela inclut également print ()` pour l'explication.

def uniqueSorted(lt):
  return sorted(list(set(lt)))

def binarySearchR(lt, n):
  return _binarySearchR(lt, n, 0, len(lt) - 1)

def _binarySearchR(lt, n, l, r):
  if l > r:
    return -1
  middleIndex = int(l + (r - l) / 2)
  middleValue = lt[middleIndex]
  print(getListIndeces(lt[l:r + 1], l))
  print(listToFormatedString(lt[l:r + 1]), middleIndex, middleValue)
  if middleValue > n:
    return _binarySearchR(lt, n, l, middleIndex - 1)
  elif middleValue < n:
    return _binarySearchR(lt, n, middleIndex + 1, r)
  else:
    return middleIndex

Je l'ai couru comme suit:

lt = [3, 6, 12, 13, 14, 16, 17, 22, 51, 56, 58, 62, 66, 70, 74, 75, 80, 92, 94, 95]
n = 70
print(binarySearchR(lt, n))

Ensuite, le résultat d'exécution suivant sera obtenu.

> 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19<
[ 3,  6, 12, 13, 14, 16, 17, 22, 51, 56, 58, 62, 66, 70, 74, 75, 80, 92, 94, 95] 9 56
>10, 11, 12, 13, 14, 15, 16, 17, 18, 19<
[58, 62, 66, 70, 74, 75, 80, 92, 94, 95] 14 74
>10, 11, 12, 13<
[58, 62, 66, 70] 11 62
>12, 13<
[66, 70] 12 66
>13<
[70] 13 70
13

Recherche de 2 minutes Version récursive Mouvement de la pile d'appels

Illustre la pile d'appels. Tout d'abord, il est poussé vers la pile d'appels avec lt comme liste et 70 comme numéro que vous voulez trouver. 9 est choisi comme indice médian. La valeur de «lt [9]» est 56, ce qui est inférieur au nombre 70 que vous voulez trouver. Par conséquent, nous allons procéder à la recherche de la seconde moitié de la liste.

BinarySearch () est exécuté comme lt [10:20] pour rechercher la seconde moitié de la liste. f (lt [10:20]) est poussé. 14 est choisi comme indice médian. La valeur de «lt [14]» est 74, ce qui est supérieur au nombre 70 que vous voulez trouver. Par conséquent, nous allons procéder à la recherche de la première moitié de la liste.

BinarySearch () est exécuté comme lt [10:14] pour poursuivre la recherche. f (lt [10:14]) est poussé. L'indice 11 est choisi. La valeur de lt [11] est 62, ce qui est inférieur au nombre 70 que vous voulez trouver. Par conséquent, nous allons procéder à la recherche de la seconde moitié de la liste.

BinarySearch () est exécuté comme lt [12:14] pour poursuivre la recherche. f (lt [12:14]) est poussé. L'indice 12 est choisi. La valeur de «lt [12]» est 66, ce qui est inférieur au nombre 70 que vous voulez trouver. Par conséquent, nous allons procéder à la recherche de la seconde moitié de la liste.

BinarySearch () est exécuté comme lt [13:14] pour poursuivre la recherche. f (lt [13:14]) est poussé. L'indice 13 est choisi. La valeur de «lt [13]» est 70, ce qui est égal au nombre 70 que vous voulez trouver. Puisqu'un nombre égal a été trouvé, il renvoie la valeur d'index de 13.

Ci-dessous, il est extrait de la pile d'appels tout en renvoyant une valeur.

Le mouvement de la pile d'appels est désormais le même que celui du plancher. On peut dire qu'il a presque la même structure, sauf pour la différence de branchement conditionnel et s'il faut traiter avec la valeur retournée.

Version non récursive de recherche de 2 minutes

La version non récursive ressemble maintenant à ceci: C'est également la même chose que le tri rapide, et il a presque la même structure que la version récursive.

def binarySearchL(lt, n):
  stack = [(0, len(lt) - 1)]
  while len(stack) > 0:
    l, r = stack.pop()
    if l > r:
      return -1
    middleIndex = int(l + (r - l) / 2)
    middleValue = lt[middleIndex]
    if middleValue > n:
      stack.append((l, middleIndex - 1))
    elif middleValue < n:
      stack.append((middleIndex + 1, r))
    else:
      return middleIndex

Dans le cas d'une recherche de 2 minutes, la pile d'appels est un mouvement simple qui ne se répète pas en augmentant et en diminuant, de sorte qu'elle peut être facilement convertie sans utiliser la pile. Ce qui suit est une version légèrement simplifiée.

def binarySearchL2(lt, n):
  l, r = 0, len(lt) - 1
  while l <= r:
    middleIndex = int(l + (r - l) / 2)
    middleValue = lt[middleIndex]
    if middleValue > n:
      l, r = l, middleIndex - 1
    elif middleValue < n:
      l, r = middleIndex + 1, r
    else:
      return middleIndex
  return -1

finalement

Certaines fonctions récursives ne répertorient que des algorithmes simples, mais le comportement de la pile d'appels est similaire pour toutes les fonctions récursives. En d'autres termes, on peut dire qu'il peut être implémenté avec une structure similaire. Après tout, je pensais que j'avais du mal à passer à une fonction non récursive car je ne comprenais pas complètement la structure de la fonction récursive. La grande différence est de savoir si vous utilisez la pile d'appels ou la pile. Ensuite, j'ai réalisé l'importance de la structure de données de base et des algorithmes appris à l'école. Les bases sont importantes. Cela signifie-t-il que les jours d'étudiants sans scrupules sont arrivés

appendice

Vérifiez / modifiez la profondeur de la pile d'appels.

Vous pouvez vérifier la profondeur de la pile d'appels python avec sys.getrecursionlimit (). Cela dépend de l'environnement, mais vous pouvez changer la profondeur avec sys.setrecursionlimit (limit).

Sirène d'arbre à 2 branches

graph TB;
    0[5]---1[3]
    0---2[4]
    1---3[1]
    1---4[2]
    4---5[0]
    4---6[1]
    2---7[2]
    2---8[3]
    7---9[0]
    7---10[1]
    8---11[1]
    8---12[2]
    12---13[0]
    12---14[1]