Rekursion ist - wie wir alle wissen - eines dieser Probleme - das Herumwickeln des Kopfes fühlt sich an, als würde man einen "Meilenstein" auf Ihrer Programmierreise erreichen.
Aber wenn es darum geht, es tatsächlich in Problemen der realen Welt zu verwenden - die Mechanik der Rekursion zu kennen, reicht NICHT aus -, muss man auch die Art der Probleme verstehen, bei denen die Rekursion die am besten geeignete Lösung ist.
Meine Frage ist also ...
- Was sind die "Problemmuster", die die Lösung der Rekursion erfordern?
- Ist Rekursion eine Form der "Divide & Conquer" -Strategie oder eine Form der "Code-Wiederverwendung" - oder ist es ein eigenständiges Entwurfsmuster?
- Können Sie uns ein Beispiel für ein Problem der realen Welt geben, bei dem Rekursion als sofortige Lösung in den Sinn kommt?
- UPDATE -
Viele Antworten beziehen sich auf "echte Probleme" als Baumdurchquerung, Fakultät usw. Ich würde "die WIRKLICHEN wirklichen Probleme" vorziehen - lassen Sie mich ein Beispiel geben ...
Wir hatten eine GROSSE Textmenge (ca. 30 MB Text als verknüpfte Liste structs) und mussten einen Index für die Volltextsuche erstellen. Wir mussten den gesamten Index im Speicher behalten und den Text alle 10 Minuten neu indizieren.
Alle 10 Minuten verglichen wir den gesamten Text (zwei verknüpfte Listen, Zeile für Zeile) mit einem neu generierten Textblock - um zu sehen, welche Zeile geändert wurde - und indizierten dann nur diese Zeile neu - auf diese Weise Wir könnten vermeiden, den GESAMTEN Text neu indizieren zu müssen. Denken Sie daran - wir mussten die Diff-Punkte zwischen zwei 30-MB-verknüpften Listen finden.
Einer meiner Kollegen hat ein fantastisches Programm entwickelt, bei dem die Linien mithilfe der SCHWEREN Rekursion verglichen wurden - und dann die Positionen gesammelt wurden, an denen sich die Spannfutter in einem Array unterschieden - ja, ich weiß, es klingt rätselhaft - wie könnte die Rekursion hier helfen - aber es tat.
Der Punkt ist - wie konnte er sehen, dass dieses Problem mit starkem Einsatz von Rekursion intelligent gelöst werden konnte?
Antworten:
Ich würde nicht sagen, dass es so etwas wie ein Problemmuster für die Verwendung von Rekursion gibt. Jede Funktion, die mit Rekursion implementiert werden kann, kann auch iterativ implementiert werden, häufig durch Drücken und Poppen eines Stapels.
Es ist eine Frage des Ausdrucks und auch der Leistung. Iterative Algorithmen weisen häufig eine bessere Leistung auf und sind einfacher zu optimieren. Rekursive Algorithmen profitieren jedoch von einem klareren Ausdruck und sind daher häufig leichter zu lesen, zu verstehen und zu implementieren.
Einige Dinge können nicht einmal ohne Rekursion ausgedrückt werden, zum Beispiel unendliche Listen. Die sogenannten funktionalen Sprachen sind stark auf Rekursion angewiesen, da dies ihre natürliche Ausdrucksweise ist. Das Sprichwort lautet: "Rekursive Programmierung ist funktionale Programmierung, die richtig gemacht wird".
Ich würde es nicht als Designmuster bezeichnen. Es ist eine Frage des Ausdrucks. Manchmal ist ein rekursiver Ausdruck einfach leistungsfähiger und ausdrucksvoller und führt somit zu besserem und saubererem Code.
Alles, was Bäume durchlaufen muss, wird durch einen rekursiven Algorithmus richtig ausgedrückt.
quelle
Weder. Teilen & Erobern verwendet Rekursion. Rekursion ist jedoch nicht unbedingt Teilen und Erobern, da letzteres bedeutet, ein Problem in zwei (oder mehr) Teile zu teilen und jeden dieser Teile symmetrisch zu lösen. In der Rekursion tun Sie dies nicht.
Die Wiederverwendung von Code hat nichts damit zu tun, und ein Entwurfsmuster kommt auf einer viel höheren Ebene ins Spiel. Zum Beispiel wird selbst Divide & Conquer (auch ein Muster auf höherer Ebene als Rekursion) immer noch nicht als Entwurfsmuster betrachtet, sondern als algorithmisches Muster.
Baumdurchquerung. Oder allgemeiner Graph Traversal. Dies umfasst insbesondere das Durchlaufen einer Ordnerstruktur.
Und natürlich alles, was Divide & Conquer oder dynamische Programmierung verwendet, da beide natürlich als Rekursion ausgedrückt werden.
quelle
Abgeleitet von der Selbstähnlichkeit von Fraktalen würde ich sagen, dass Selbstgleichheit oder Selbstidentität (oder wie auch immer es genannt wird) ein typisches Problemmuster für die Rekursion ist. Das heißt, ein Problem kann in Unterprobleme aufgeteilt werden, die dieselbe Struktur wie das Hauptproblem haben.
Bei der erwähnten Baumdurchquerung ist jeder Unterbaum ein vollständiger Baum für sich, genau wie der Hauptbaum, und der Hauptbaum kann ein Unterbaum innerhalb eines anderen Baums sein.
Ich vermute also, dass Ihr Kollege die Selbstgleichheitseigenschaften Ihres Indexierungsproblems entdeckt hat. Oder er ging umgekehrt und verwandelte das Problem in eine selbstgleiche Darstellung.
quelle
Nun, Rekursion kann leicht verstanden werden, wenn man versucht, Imperativschleifen in funktionale Funktionen umzuwandeln. Wie auch immer, versuchen wir, alle Fragen zu beantworten:
Wenn Sie eine baumartige Struktur oder einen baumartigen Algorithmus haben, benötigen Sie eine Rekursion. Wenn sich Ihr zwingender Code mit einem Stapel befasst, benötigen Sie eine Rekursion. Wenn ein bestimmter Schritt in Ihrem Algorithmus von vorherigen Schritten abhängt (Think Loops), müssen Sie eine Rekursion durchführen. Notwendigkeit hier ist zu interpretieren, wie verwendet werden kann.
Keiner. Teilen und Erobern verwendet Rekursion, kann aber mit Stapeln implementiert werden. Die Wiederverwendung von Code bezieht sich auf etwas anderes. Entwurfsmuster sind komplizierter als einfache Rekursion.
Parsen und alles, was mit Baumstrukturen zu tun hat. Auch implizite Baumstrukturen.
quelle
Wenn es eine Möglichkeit gibt, es so zu vereinfachen, dass es einfach ist, kann dies der Hinweis sein, dass eine Rekursion funktionieren könnte. Sie können sortieren und nach Beispielen suchen, in denen rekursive Lösungen wie Merge Sort bzw. Binary Search vorhanden sind.
Zu beachten ist, wie einige Probleme mit einer Rekursion wie einer Fakultät schlecht gelöst werden können.
In einem Beispiel aus der Praxis, in dem ich die Rekursion verwenden würde, kann das Nachschlagen eines Buches aus einem Bücherregal ganz einfach auf rekursive Weise erfolgen. Ich schaue mir nur das Buch an und wenn es nicht das ist, was ich will, gehe ich zum nächsten über. Ich höre auf, wenn ich entweder das Buch finde oder das Ende der Reihe erreicht habe. Die Schleife beim Überprüfen eines Buches und beim Weitergehen zum nächsten kann rekursiv erfolgen. Vielleicht ist dies ein zu reales Beispiel.
quelle
Ganz allgemein ist eine Rekursion erforderlich, wenn Sie ein Problem lösen, bei dem f (x) = f (g (x)) . Wenn Sie mit der unendlichen Rekursion nicht einverstanden sind, sollte g (x) nicht zu x ausgewertet werden .
Nichts des oben Genannten. Es ist nur eine Möglichkeit, dasselbe wiederholt zu tun, manchmal basierend auf Variationen der Eingabe. Das Konzept gibt es schon viel länger als Entwurfsmuster, Wiederverwendung von Code oder sogar Computer.
Fakultäten, die Fibonacci-Sequenz, das Durchqueren von Bäumen und viele andere Probleme können durch Rekusion gelöst werden. Rekursion im Sinne einer Funktion, die sich selbst aufruft, ist nicht unbedingt der beste Weg, um solche Dinge zu implementieren. Es gibt andere Möglichkeiten, um den gleichen Effekt zu erzielen (z. B. einen Stapel und eine Schleife), die möglicherweise wünschenswerter sind.
quelle
Wenn Sie einen rekursiven Algorithmus schreiben, übersetzen Sie normalerweise eine rekursive Definition des Problems in den Code. Dann müssen Sie nicht einmal wissen, wie es ausgeführt wird.
Das passiert in der funktionalen Programmierung. Tatsächlich geben Sie an, was (Definition) und nicht wie . Mit anderen Worten, Sie definieren die Basis und definieren dann Ihr Problem im Begriff eines Unterproblems.
Betrachten Sie zum Beispiel den
FactorialAlgorithmusWenn Sie dann auf ein Problem stoßen, sollten Sie sich überlegen, ob Sie es rekursiv definieren können oder nicht. Wenn Sie es rekursiv definieren können, haben Sie es fast gelöst.
Eine rekursive Funktion sollte jedoch keine rekursive Definition sein. Sie können die Basis definieren und die Lösung des Hauptproblems mit der Lösung (Definition) von Unterproblemen in Beziehung setzen (definieren). Für diese Beziehung benötigen Sie möglicherweise ein Verfahren.
Ein Beispiel ist ,
MergeSortin demmergeeine imperative Verfahren könnte die Definition oder Lösung des Sortierens das gesamte Array auf die Sortierung der Subarrays zu beziehen.quelle