Betrachten Sie die Konvertierung von Python rekursiv in nicht rekursiv

Einführung

Rekursive Funktionen sind zwar praktisch, haben aber auch Nachteile. Aus diesem Grund wurden rekursive Funktionen seit langem in nicht rekursive Funktionen konvertiert. Die Konvertierung selbst wurde durchgeführt, war aber zufällig und ich habe theoretisch nicht darüber nachgedacht, warum sie konvertiert werden kann. Ich wollte theoretisch über den Konvertierungsprozess nachdenken, konnte aber die Gelegenheit nicht nutzen. In der Zwischenzeit nahm der Artikel über rekursive Funktionen zu, und ich begann, Artikel zu schreiben. (Es ist lange her, seit ich es in Ruhe gelassen habe) Ein weiterer Faktor ist, dass ich ein anderes Programm geschrieben und die Bedeutung des Stapelns erkannt habe.

Es leugnet jedoch nicht die Nützlichkeit rekursiver Funktionen. Ich liebe rekursive Funktionen.

Angenommener Leser

Die Programmiersprache kann alles sein, also werde ich Python verwenden. Ich werde den Algorithmus selbst, der zum Erstellen des rekursiven Programms verwendet wird, nicht erklären. Daher ist es für diejenigen gedacht, die Python verstehen und Algorithmen verstehen (untersuchen).

Stack und Stack aufrufen

Der Stack, der die Ausführung des Programms steuert, heißt Call Statck. Es wird auch als Ausführungsstapel, Kontrollstapel, Funktionsstapel usw. bezeichnet. In diesem Artikel werden wir mit dem Aufrufstapel vereinheitlichen. Außerdem wird der Stapel als Datenstruktur einfach als Stapel bezeichnet.

Warum rekursive Funktionen vermieden werden können

Rekursive Funktionen verwenden den Aufrufstapel, indem sie die Funktion aufrufen. Es gibt eine Obergrenze für die Kapazität, die im Aufrufstapel gespeichert werden kann. Die Kapazität kann durch Ändern der Einstellungen des Compilers usw. geändert werden, ist jedoch noch begrenzt. (Ich habe es in letzter Zeit berührt, daher weiß ich nicht, wie flexibel es ist.) Wenn die Kapazität des Aufrufstapels überschritten wird, tritt ein Stapelüberlauf auf und die Programmausführung wird gestoppt. Im Prinzip verbrauchen rekursive Funktionen eine große Menge an Aufrufstapel und verursachen einen Stapelüberlauf. Es hängt von den Einstellungen ab, aber meiner Erfahrung nach, die nicht so viele sind, ist es einfach, den Aufrufstapel zu verbrauchen und einen Stapelüberlauf zu verursachen. (Vielleicht liegt es an deinem Mistprogramm) Daher wird es tendenziell vermieden.

Andererseits ist der vom Stapel verwendete Heap-Speicher relativ flexibler als der Aufrufstapel. (Ich denke, das hängt auch von den Einstellungen und dem zu erstellenden Programm ab.) Daher werden wir zur Verwendung des Stapels wechseln.

In letzter Zeit gibt es Compiler mit einer Funktion namens Tail-Receipt-Optimierung, die Tail-Receipt in eine Schleifenstruktur umwandelt. Es wird besser, ohne sich zu viele Sorgen machen zu müssen. Es wird bequemer.

Conversion-Richtlinie

In diesem Artikel halte ich es für eine typische Konvertierungsmethode, aber ich möchte in Betracht ziehen, eine rekursive Funktion mithilfe eines Stapels zu einer nicht rekursiven Funktion zu machen. Dies ist ein Bild des Umschaltens der Verwendung des Aufrufstapels auf die Verwendung des Stapels.

Bodenbelag

Betrachten Sie zunächst einen einfachen Boden als Beispiel.

Hierarchische rekursive Version

Die Implementierung der Hierarchie unter Verwendung von rekursiv ist wie folgt.

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

Hierarchische rekursive Aufrufstapelbewegung

Lassen Sie uns veranschaulichen, wie der Aufrufstapel aussieht, wenn diese Funktion mit n = 5 ausgeführt wird. Es ist keine strenge Operation, sondern eine Bildbewegung. Wenn die Funktion ausgeführt wird, schiebt sie zuerst den Aufruf selbst "factorialR (5)" an den Aufrufstapel. factorialR (5) wird bei Ausführung in5 * factorialR (4)umgewandelt.

Rufen Sie dann factorialR (4) auf und schieben Sie es in den Aufrufstapel. factorialR (4) wird bei Ausführung in4 * factorialR (3)umgewandelt.

Im Folgenden funktioniert es auf die gleiche Weise.

Der rekursive Aufruf wurde fortgesetzt, bis n = 0 war.

Wenn n = 0 ist, wird 1 zurückgegeben.

Wenn factorialR (0) ausgeführt und 1 zurückgegeben wird, wird der Aufrufstapel um eins verringert. Dann kehrt es zu dem Zeitpunkt zurück, zu dem n = 1 aufgerufen wird, "1 * Fakultät R (0)" aufgelöst wird und "1 * 1 = 1" zurückgegeben wird.

In ähnlicher Weise verringert die Rückgabe des vorherigen Ausführungsergebnisses den Aufrufstapel um eins. Es kehrt zu dem Punkt zurück, an dem n = 2 aufgerufen wird und "2 * Fakultät R (1)" aufgelöst wird und "2 * 1 = 2" zurückgegeben wird. Im Folgenden funktioniert es auf die gleiche Weise.

Schließlich wird "5 * Fakultät R (4) = 5 * 24 = 120" und 120 zurückgegeben.

In der rekursiven Version wird der Aufruf rekursiv ausgeführt, sodass der Aufruf auf dem Aufrufstapel gestapelt wird. Ich möchte die Struktur der Funktion beibehalten und nicht den Aufrufstapel verwenden. Die obige Funktion erforderte das Berechnungsergebnis in der Mitte und das Argument, das für den nächsten Funktionsaufruf zur Berechnung der Leistung verwendet wurde. Versuchen wir daher, das Berechnungsergebnis in der Mitte in eine Variable und den Wert für den nächsten Funktionsaufruf auf dem Stapel zu setzen. Im Fall von "5 * f (4)" wird 5 auf die Variable und 4 auf den Stapel gelegt. Basierend auf dieser Idee möchte ich eine nicht rekursive Version erstellen.

Nicht rekursive Version

Lassen Sie uns noch einmal das Verhalten des Stapels veranschaulichen, wenn n = 5 ist. Wenn die Funktion startet, drückt sie zuerst 5 auf den Stapel. Setzen Sie außerdem die Variable Ergebnis, mit der das Berechnungsergebnis in der Mitte gespeichert wird, auf 1.

Der nächste Schritt besteht darin, den Stapel zu öffnen und den Wert 5 abzurufen. Dann multiplizieren Sie das Ergebnis mit dem abgerufenen Wert. Schieben Sie zum Schluss den Wert 4 von "5-1 = 4" auf den Stapel.

Der nächste Schritt besteht darin, den Stapel zu öffnen, um den Wert 4 abzurufen. Dann multiplizieren Sie das Ergebnis mit dem abgerufenen Wert. Schieben Sie zum Schluss den Wert 3 von "5-1 = 3" auf den Stapel.

Im Folgenden funktioniert es auf die gleiche Weise.

Geben Sie den Wert 0 ein und multiplizieren Sie das Ergebnis mit 1. Wenn 0, gibt es keinen nächsten Wert, der auf den Stapel gedrückt werden kann.

Nachdem der Stapel verschwunden ist, wird der Ergebniswert von 120 als Antwort auf die Potenz von n = 5 gesucht. Ich denke, Sie können die Bedeutung der Verwendung des Stapels finden, weil der Boden einfach ist. Ich mache dies jedoch zur Verallgemeinerung der Konvertierung. Machen wir es zu einer darauf basierenden Funktion. Um ehrlich zu sein, wäre es wie folgt?

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

Hierarchie nicht rekursive Version Teil 2

Stellen Sie sich eine Implementierung vor, die das Verhalten der rekursiven Version des Aufrufstapels auf dem Stapel reproduziert. Bewegen wir den Stapel wie folgt.

Wenn n = 0 ist, ist es "0! = 1", also ist 1 fest.

Dann platzen Sie die bestätigte 1 und brechen Sie einen Stapel. Speichern Sie diese geknallte 1 als Ergebnis.

Geben Sie dann den Top-Wert 1 ein und brechen Sie einen Stapel. Berechnen Sie "1 * 1" mit der zuvor gespeicherten 1 und der gerade gepoppten 1 und speichern Sie "1" als Ergebnis. Dies bestätigt den Wert von n = 1. Im Folgenden wird es auf die gleiche Weise ausgeführt.

Pop den Top-Wert 2 und multiplizieren Sie ihn mit dem Ergebniswert 1, um das Ergebnis 2 im Ergebnis zu erhalten.

Pop den Top-Wert 3 und multiplizieren Sie ihn mit dem Ergebniswert 2, um das Ergebnis 6 im Ergebnis zu erhalten.

Pop den Top-Wert 4 und multiplizieren Sie ihn mit dem Ergebniswert 6, um das Ergebnis 24 im Ergebnis zu erhalten.

Pop den Top-Wert 5 und multiplizieren Sie ihn mit dem Ergebniswert 24, um das Ergebnis 120 im Ergebnis zu erhalten.

Nachdem der Stapel verschwunden ist, wird der Ergebniswert von 120 als Antwort auf die Potenz von n = 5 gesucht.

Wäre es in diesem Fall wie folgt?

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

Hierarchie nicht rekursive Versionsvereinfachung

Eine etwas sauberere Implementierung sieht folgendermaßen aus:

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)

Fibonacci-Folge

Als nächstes möchte ich die Fibonacci-Sequenz als Beispiel nehmen.

Rekursive Version der Fibonacci-Sequenz

Eine typische Implementierung mit Fibonacci-Sequenzwiederholung würde folgendermaßen aussehen: Der große Unterschied zum Bodenbelag besteht darin, dass Sie sich zweimal in einem Lauf anrufen.

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

Rekursives Aufrufstapelverhalten der Fibonacci-Sequenz

Lassen Sie uns den Zustand des Aufrufstapels veranschaulichen, wenn n = 5 ist, wie im Fall von Bodenbelägen. Wenn die Funktion ausgeführt wird, wird "fibonacciR (5)" zuerst auf den Aufrufstapel verschoben. Dann wird es in "FibonacciR (3) + FibonacciR (4)" umgewandelt.

Dann wird "fibonacciR (3)" aufgerufen und in den Aufrufstapel geschoben. Bei der Ausführung wird es in "fibonacciR (1) + fibonacciR (2)" konvertiert.

Dann wird "fibonacciR (1)" aufgerufen und in den Aufrufstapel geschoben. fibonacciR (1) gibt bei Ausführung 1 zurück. Dies löst teilweise "FibonacciR (1) + FibonacciR (2)" auf, wenn "FibonacciR (3)" aufgerufen wird, um "1 + FibonacciR (2)" zu werden.

Um "fibonacciR (2)" aufzulösen, wird es aufgerufen und in den Aufrufstapel verschoben. Bei der Ausführung wird es in "fibonacciR (0) + fibonacciR (1)" konvertiert.

fibonacciR (0) wird aufgerufen und in den Aufrufstapel verschoben. fibonacciR (0) gibt bei Ausführung 0 zurück. Dies löst teilweise "fibonacciR (0) + fibonacciR (1)" auf, wenn "fibonacciR (2)" aufgerufen wird, um "0 + fibonacciR (1)" zu werden.

In ähnlicher Weise wird "fibonacciR (1)" aufgerufen und in den Aufrufstapel verschoben. fibonacciR (1) gibt bei Ausführung 1 zurück. Dies löst "0 + fibonacciR (1)" auf, wenn "fibonacciR (2)" auf "0 + 1 = 1" aufgerufen wird.

"1 + fibonacciR (1)" beim Aufrufen von "fibonacciR (3)" wird in "1 + 1 = 2" aufgelöst.

Beim Aufruf von "fibonacciR (5)" wird ein Teil von "fibonacciR (3) + fibonacciR (4)" in "2 + fibonacciR (4)" aufgelöst.

Es funktioniert genauso wie unten.

Es funktioniert wie oben und gibt den Wert 5 zurück, wenn n = 5 ist. Ich habe es lange geschrieben, aber das Verhalten des Aufrufstapels ist so. Dies allein ist schwer zu verstehen, daher möchte ich eine Halbierende verwenden, um die Bewegung dieses Aufrufstapels darzustellen.

Rekursive Version des Halbbaums der Fibonacci-Sequenz

Als Baum mit zwei Zweigen ausgedrückt, ist es wie folgt.

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]

Sie können sehen, dass die Tiefe des Aufrufstapels der Tiefe des Halbbaums entspricht. Sie können auch sehen, dass die Reihenfolge, in der die Werte aufgelöst werden, der Suchreihenfolge der Suche mit Tiefenpriorität des gegabelten Baums entspricht. Die Suche mit Tiefenpriorität nach gegabelten Bäumen wird häufig als mithilfe von Stapeln implementiert beschrieben. Hier wird es mit dem Call Stack implementiert.

Als nächstes möchte ich eine nicht rekursive Version erstellen.

Nicht rekursive Version der Fibonacci-Sequenz

Die rekursive Version der Fibonacci-Sequenz ist ebenfalls eine einfache Funktion, und in der Mitte befindet sich kein Berechnungsergebnis. Was also auf den Stapel gelegt werden soll, ist, die an die Funktion übergebenen Argumente auf den Stapel zu legen.

Lassen Sie uns die Stapelsituation veranschaulichen, wenn n = 5 wie zuvor ist. Wenn es zu laufen beginnt, schiebt es das erste gegebene Argument 5 auf den Stapel.

Der nächste Schritt besteht darin, den Stapel zu öffnen und 5 abzurufen. 5 kann den Wert nicht aus der Graduierungsformel der Fibonacci-Sequenz bestimmen. Stattdessen werden wir nach "n-2" und "n-1" fragen. Mit anderen Worten, drücken Sie "5-2 = 3" bzw. "5-1 = 4" auf den Stapel. Ich werde von der größten Zahl zuerst pushen.

Der nächste Schritt besteht darin, den Stapel zu öffnen und 3 abzurufen. 3 kann den Wert nicht bestimmen, drücken Sie stattdessen 1 bzw. 2.

Der nächste Schritt besteht darin, den Stapel zu öffnen und die 1 abzurufen. 1 kann als Wert bestimmt werden, speichern Sie ihn also als Ergebnis.

Der nächste Schritt besteht darin, den Stapel zu öffnen und 2 abzurufen. 2 kann den Wert nicht bestimmen, drücken Sie stattdessen 0 bzw. 1.

Der nächste Schritt besteht darin, den Stapel zu öffnen und Nullen abzurufen. Da 0 als Wert bestimmt werden kann, fügen Sie ihn zum Ergebnis hinzu und speichern Sie ihn.

Der nächste Schritt besteht darin, den Stapel zu öffnen und die 1 abzurufen. Da 1 als Wert bestimmt werden kann, fügen Sie ihn zum Ergebnis hinzu und speichern Sie ihn.

Im Folgenden funktioniert es auf die gleiche Weise.

Es funktioniert wie oben und gibt auch den Wert 5 zurück, wenn n = 5 ist. Ich würde das gerne wieder ehrlich umsetzen.

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

Ich entschied mich für eine Implementierung ähnlich dem Bodenreiten. (Obwohl ich versuche, eine ähnliche Implementierung zu haben)

Vereinfachung der nicht rekursiven Version der Fibonacci-Sequenz

Wenn Sie nur die Antwort wünschen, ohne den Stapel zu kennen, können Sie auch Folgendes tun. Im Fall von Stapeln wurde es aus dem mit dem größeren Koeffizienten des allmählichen Ausdrucks berechnet, wie z. B. "n-> n-1-> n-2-> ...-> 0". Dies wird aus dem mit dem kleineren Koeffizienten berechnet, wie z. B. "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

Schnelle Sorte

Als nächstes betrachten Sie eine schnelle Sortierung.

Schnelle Sortierung rekursiver Version

Ich habe versucht, die schnelle Sortierung wie folgt rekursiv zu implementieren. Ich versuche, doppelte Werte zu erhalten. Ich denke, es gibt einige Unterschiede zur typischen Implementierung, aber ich denke, es ist eine schnelle Sortierung. Ich habe "print ()" eingefügt, um den Sortiervorgang zu zeigen. Zu diesem Zweck definieren und verwenden wir auch Hilfsfunktionen. isSorted () bestimmt, ob es sortiert ist.

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)

Geben Sie "[7, 2, 1, 4, 6, 0, 8, 5, 9, 3]" als Argument an und führen Sie es aus.

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

Anschließend wird das folgende Ausführungsergebnis angezeigt.

   >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

Schnelles Sortieren des Verhaltens des rekursiven Aufrufstapels

Die schnelle Sortierung zeigt auch die Bewegung des Aufrufstapels. Zuerst wird es als "f (lt)" in den Aufrufstapel verschoben.

6 wird anfänglich als Drehpunkt ausgewählt, Werte unter 6 werden an den Anfang der Liste verschoben und Werte über 6 werden an den Anfang der Liste verschoben. Da der Grenzindex 6 ist, wird "quickSort ()" als Ergebnis der Sortierung bei "lt [0: 6]" bzw. "lt [7:10]" ausgeführt. Der Wert des Grenzindex ist der Drehpunkt. Wenn doppelte Werte vorhanden sind, befindet sich der als Drehpunkt ausgewählte Wert möglicherweise in der sortierten Liste. Der Grenzindex wird sortiert und die Position festgelegt. Das Element, dessen Position festgelegt ist, wird als "Ergebnis" angezeigt.

Der Aufrufstapel wird dann mit "f (lt [0: 6])" zur Ausführung verschoben.

Hier wird 1 als Drehpunkt gewählt, wobei Werte kleiner als 1 vorwärts und Werte größer als 1 rückwärts geteilt werden. Der Begrenzerindex ist 1, und "quickSort ()" wird auf "lt [0: 1]" bzw. "lt [2: 6]" ausgeführt.

F (lt [0: 1]) wird auf den Aufrufstapel verschoben.

lt [0: 1] hat eine Länge von 1, wird also positioniert und aus dem Aufrufstapel entfernt.

Der Aufrufstapel kehrt zurück, dann wird der Bereich von "lt [2: 6]" sortiert. Hier wird 4 als Drehpunkt gewählt und in einen Wertebereich von weniger als 4 und Werte von mehr als 4 unterteilt. Der Begrenzerindex ist 4, und "quickSort ()" wird auf "lt [2: 4]" bzw. "lt [5: 6]" ausgeführt. Stellen Sie die Position von "lt [4]" fest.

F (lt [2: 4]) wird auf den Aufrufstapel verschoben.

2 wird als Drehpunkt gewählt und in weniger als 2 und mehr als 2 unterteilt. quickSort () wird bei lt [2: 2] bzw. lt [3: 4] ausgeführt, getrennt durch einen Begrenzerindex von 2. lt [2] wird bestätigt.

Sowohl "lt [2: 2]" als auch "lt [3: 4]" werden ausgeführt, aber die Position ist fest, da die Länge des Bereichs 1 oder weniger beträgt. f (lt [2: 2]) wird gedrückt und gepoppt, weil es 0 lang ist. f (lt [3: 4]) wird ausgeführt, die Position von lt [3] ist festgelegt und es wird geknallt.

Der Aufrufstapel kehrt zurück, dann wird der Bereich von "lt [5: 6]" sortiert. Da lt [5: 6] auch einen Bereich von 1 hat, ist die Position fest und knallt. Die erste Hälfte der Liste ist jetzt sortiert und bestätigt. Die zweite Hälfte wird auf die gleiche Weise verarbeitet.

9 wird als Drehpunkt gewählt und in "lt [7: 9]" und "lt [9: 9]" unterteilt. lt [9] wird bestätigt.

f (lt [7: 9]) wird gedrückt.

8 wird als Drehpunkt gewählt und in "lt [7: 8]" und "lt [8: 8]" unterteilt. lt [8] wird bestätigt.

f (lt [7: 8]) wird gedrückt.

Die Position von "lt [7]" ist fest.

Sowohl lt [8: 8] als auch lt [9: 9] haben eine Länge von 0, sodass sie enden, ohne etwas zu tun, und der Prozess endet.

Sie können sehen, dass es jetzt dem Verhalten des Aufrufstapels in der Fibonacci-Sequenz ähnlich ist.

Schnelle Sortierung nicht rekursiver Version

Die schnelle Sortierung wird auch in nicht rekursiv konvertiert. Der Prozess des Stapelns auf dem Aufrufstapel wird auf die gleiche Weise wie die herkömmliche Denkweise auf dem Stapel gestapelt. Bei der schnellen Sortierung wird der Bereich, der als nächstes sortiert werden muss, auf dem Stapel gestapelt. Die Implementierung sieht folgendermaßen aus: Ich dachte, es wäre ein Schmerz, aber es ist fast das gleiche wie in der retrospektiven Version.

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))

2-minütige Suche

An dieser Stelle ist es ein Slapstick, aber ich würde gerne eine zweiminütige Suche in Betracht ziehen.

2-minütige rekursive Suchversion

Zunächst ist es eine rekursive Version, aber ich habe sie wie folgt implementiert. Dies setzt voraus, dass Sie eine sortierte Liste mit eindeutigen Werten übergeben. Sie können "uniqueSorted ()" verwenden, um eine Liste zu erstellen, die Ihren Kriterien entspricht. Dies beinhaltet auch "print ()" zur Erklärung.

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

Ich habe es wie folgt ausgeführt:

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))

Dann wird das folgende Ausführungsergebnis erhalten.

> 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

2-minütige Suche Rekursive Version Aufruf der Stapelbewegung

Veranschaulicht den Aufrufstapel. Zuerst wird es mit lt als Liste und 70 als der Nummer, die Sie finden möchten, zum Aufrufstapel verschoben. Als Medianindex wird 9 gewählt. Der Wert von "lt [9]" ist 56, was weniger als die Zahl 70 ist, die Sie finden möchten. Daher werden wir mit der Suche nach der zweiten Hälfte der Liste fortfahren.

BinarySearch () wird als lt [10:20] ausgeführt, um die zweite Hälfte der Liste zu durchsuchen. f (lt [10:20]) wird gedrückt. Als Medianindex wird 14 gewählt. Der Wert von lt [14] ist 74, was größer ist als die Zahl 70, die Sie finden möchten. Daher werden wir mit der Suche nach der ersten Hälfte der Liste fortfahren.

BinarySearch () wird als lt [10:14] ausgeführt, um mit der Suche fortzufahren. f (lt [10:14]) wird gedrückt. Index 11 wird gewählt. Der Wert von "lt [11]" ist 62, was weniger als die Zahl 70 ist, die Sie finden möchten. Daher werden wir mit der Suche nach der zweiten Hälfte der Liste fortfahren.

BinarySearch () wird als lt [12:14] ausgeführt, um mit der Suche fortzufahren. f (lt [12:14]) wird gedrückt. Index 12 wird gewählt. Der Wert von "lt [12]" ist 66, was weniger als die Zahl 70 ist, die Sie finden möchten. Daher werden wir mit der Suche nach der zweiten Hälfte der Liste fortfahren.

BinarySearch () wird als lt [13:14] ausgeführt, um mit der Suche fortzufahren. f (lt [13:14]) wird gedrückt. Index 13 wird gewählt. Der Wert von lt [13] ist 70, was der Zahl 70 entspricht, die Sie suchen möchten. Da eine gleiche Zahl gefunden wurde, wird der Indexwert 13 zurückgegeben.

Danach wird es aus dem Aufrufstapel entfernt, während der Wert zurückgegeben wird.

Die Bewegung des Aufrufstapels entspricht jetzt der des Fußbodens. Es kann gesagt werden, dass es fast die gleiche Struktur hat, mit Ausnahme des Unterschieds in der bedingten Verzweigung und der Frage, ob mit dem zurückgegebenen Wert verarbeitet werden soll.

2-minütige Suche nicht rekursive Version

Die nicht rekursive Version sieht jetzt so aus: Dies entspricht auch der schnellen Sortierung und hat fast die gleiche Struktur wie die rekursive Version.

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

Bei einer 2-minütigen Suche ist der Aufrufstapel eine einfache Bewegung, die das Erhöhen und Verringern nicht wiederholt, sodass er ohne Verwendung des Stapels problemlos konvertiert werden kann. Das Folgende ist eine leicht vereinfachte Version.

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

Schließlich

Einige rekursive Funktionen listen nur einfache Algorithmen auf, aber das Aufrufstapelverhalten ist für alle rekursiven Funktionen ähnlich. Mit anderen Worten kann gesagt werden, dass es mit einer ähnlichen Struktur implementiert werden kann. Schließlich dachte ich, dass es mir schwer fällt, in eine nicht rekursive Funktion zu konvertieren, weil ich die Struktur der rekursiven Funktion nicht vollständig verstanden habe. Der große Unterschied besteht darin, ob Sie den Aufrufstapel oder den Stapel verwenden. Dann erkannte ich die Bedeutung der grundlegenden Datenstruktur und der in der Schule erlernten Algorithmen. Die Grundlagen sind wichtig. Bedeutet das, dass die skrupellosen Studententage vorüber sind (´ ・ ω ・ \ `)

Blinddarm

Überprüfen / ändern Sie die Tiefe des Aufrufstapels.

Sie können die Tiefe des Python-Aufrufstapels mit sys.getrecursionlimit () überprüfen. Dies hängt von der Umgebung ab, aber Sie können die Tiefe mit "sys.setrecursionlimit (limit)" ändern.

2 Astbaum Meerjungfrau

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]