Hallo Habr! Ich präsentiere Ihnen die Übersetzung des Artikels "Entfernen einer Rekursion in Python, Teil 1" von Eric Lippert.
In den letzten 20 Jahren habe ich die Einfachheit und Leistungsfähigkeit von Python bewundert, obwohl ich nie wirklich damit gearbeitet oder im Detail studiert habe.
Vor kurzem habe ich ihn mir genau angesehen - und es stellte sich heraus, dass es eine wirklich schöne Sprache war.
Bei einer kürzlich gestellten Frage zu StackOverflow habe ich mich gefragt, wie ein rekursiver Algorithmus in einen iterativen Algorithmus konvertiert werden kann, und es stellte sich heraus, dass Python eine ziemlich gute Sprache dafür ist.
Das Problem, auf das der Autor der Frage gestoßen ist, war wie folgt:
- Der Spieler befindet sich in einer beliebigen Zelle auf einem nummerierten Feld.
- Das Ziel ist es, zu Zelle Nummer 1 zurückzukehren;
- Befindet sich der Spieler auf einem geraden Feld, zahlt er eine Münze und geht den halben Weg zur Zelle Nr. 1;
- Befindet sich der Spieler auf einem ungeraden Feld, kann er 5 Münzen bezahlen und direkt zum ersten Feld gehen oder eine Münze bezahlen und einen Schritt zum Feld Nr. 1 machen - auf einem geraden Feld.
Die Frage ist: Was ist die geringste Menge an Münzen, die Sie bezahlen müssen, um von der aktuellen Zelle zur ersten zurückzukehren?
Die Aufgabe hat eine offensichtliche rekursive Lösung:
def cost(s): if s <= 1: return 0 if s % 2 == 0: return 1 + cost(s // 2) return min(1 + cost(s - 1), 5)
Dieses Programm stürzte jedoch ab und erreichte die maximale Rekursionstiefe, höchstwahrscheinlich aufgrund der Tatsache, dass der Autor der Frage mit sehr großen Zahlen experimentierte.
Daher stellt sich die Frage: Wie kann ein rekursiver Algorithmus in Python in einen iterativen Algorithmus umgewandelt werden?
Bevor wir beginnen, möchte ich darauf hinweisen, dass es natürlich schnellere Lösungen für dieses spezielle Problem gibt, an sich ist es nicht sehr interessant.
Vielmehr diente diese Aufgabe nur als Ausgangspunkt für die Frage, wie im allgemeinen Fall ein einzelner rekursiver Aufruf in einem Python-Programm entfernt werden kann.
Der Punkt ist, dass Sie jede einfache rekursive Methode konvertieren und die Rekursion loswerden können, und dies ist nur ein Beispiel, das zur Hand war.
Die Technik, die ich zeigen werde, stimmt natürlich nicht genau mit der Schreibweise von Python überein. Wahrscheinlich würde eine Lösung im Python-Stil Generatoren oder andere Funktionen der Sprache verwenden.
Was ich hier zeigen möchte, ist, wie man die Rekursion mithilfe einer Folge kleiner und sicherer Transformationen beseitigt und die Funktion zu einer Form führt, in der es einfach ist, die Rekursion durch eine Iteration zu ersetzen.
Lassen Sie uns zunächst sehen, wie Sie das Programm in dieses Formular bringen.
Im ersten Schritt unserer Konvertierung möchte ich, dass die vor dem rekursiven Aufruf durchgeführten Berechnungen auf die Berechnung des Arguments reduziert werden und die Berechnungen nach dem rekursiven Aufruf in einer separaten Methode ausgeführt werden, die das Ergebnis des rekursiven Aufrufs akzeptiert.
def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s <= 1: return 0 if s % 2 == 0: argument = s // 2 result = cost(argument) return add_one(result) argument = s - 1 result = cost(argument) return get_min(result)
Der zweite Schritt, den ich machen möchte, ist die Berechnung des Arguments in einer separaten Funktion:
Im dritten Schritt möchte ich eine Hilfsfunktion hinzufügen, die die Fortsetzungsfunktion auswählt, die nach der Rückkehr von der Rekursion aufgerufen wird.
Beachten Sie, dass die Hilfsfunktion eine Funktion zurückgibt.
Jetzt schreiben wir es in einer allgemeineren und prägnanteren Form:
Es ist ersichtlich, dass jede vorgenommene Änderung die Bedeutung des Programms beibehielt.
Jetzt wird die Prüfung auf die Parität der Zahl zweimal durchgeführt, obwohl vor den Änderungen eine Prüfung durchgeführt wurde.
Wenn wir wollen, können wir dieses Problem lösen, indem wir zwei Hilfsfunktionen zu einer kombinieren, die ein Tupel zurückgibt.
Aber machen wir uns im Rahmen dieser Aufgabe keine Sorgen.
Wir haben unsere rekursive Methode auf die allgemeinste Form reduziert.
- Im Basisfall:
- Berechnen Sie den zurückzugebenden Wert.
- gib es zurück.
- In einem nicht grundlegenden Fall:
- Berechnen Sie das Rekursionsargument.
- einen rekursiven Aufruf machen;
- Berechnen Sie den Rückgabewert.
- gib es zurück.
Ein wichtiger Punkt, auf den Sie bei diesem Schritt achten müssen, ist, dass after keine cost selbst enthalten sollte.
Die hier gezeigte Methode entfernt einen einzelnen rekursiven Aufruf.
Wenn Sie zwei oder mehr Rekursionen haben, benötigen wir eine andere Lösung.
Sobald wir unseren rekursiven Algorithmus in diese Form gebracht haben, ist es bereits einfach, ihn in eine iterative zu konvertieren.
Der Trick besteht darin, sich vorzustellen, was in einem rekursiven Programm passiert.
So führen wir einen rekursiven Abstieg durch: Wir rufen get_argument vor dem rekursiven Aufruf auf und rufen die after- Funktion auf, nachdem wir von der Rekursion zurückgekehrt sind.
Das heißt, alle Aufrufe von get_argument erfolgen vor allen Aufrufen von get_argument .
Daher können wir dies in zwei Zyklen konvertieren: Der erste ruft get_argument auf und bildet eine Liste von After- Funktionen, und der zweite ruft alle After- Funktionen auf:
Keine Rekursion mehr!
Es sieht aus wie Magie, aber alles, was wir hier tun, ist dasselbe wie die rekursive Version des Programms und in derselben Reihenfolge.
Dieses Beispiel spiegelt den Gedanken wider, den ich oft über den Aufrufstapel wiederhole: Sein Zweck ist es, zu kommunizieren, was als nächstes passieren wird und nicht, was bereits passiert ist!
Die einzige nützliche Information über den Aufrufstapel in der rekursiven Version des Programms ist der Nachwert, da diese Funktion als nächstes aufgerufen wird und alles andere auf dem Stapel nicht wichtig ist.
Anstatt den Aufrufstapel als ineffiziente und umständliche Methode zum Speichern des After- Stacks zu verwenden, können wir einfach den After- Function-Stack speichern.
Das nächste Mal werden wir uns einen komplexeren Weg ansehen, um die Rekursion in Python zu entfernen.