Algorithmus rekursiv: Beschreibung, Analyse, Eigenschaften und Beispiele

Ein Modernes Verständnis von Rekursion: Bestimmung der Funktionalität und greifen Sie von außen und von dieser Funktionalität. Es wird angenommen, dass die Rekursion geboren war Mathematiker: Berechnung der faktorielle, endlose Reihen, Fraktale, kontinuierliche Brüche... Aber Rekursion kann man überall entdecken. Objektive Naturgesetze „glauben“ Rekursion seinen grundlegenden Algorithmus und Ausdrucksform (der Existenz) nicht so viel Gegenstände der materiellen Welt, wie überhaupt der wichtigste Algorithmus der Bewegung.

Die Menschen verschiedener Berufe in verschiedenen Bereichen der Wissenschaft und Technik verwendet einen rekursiven Algorithmus f (x), wo „x ~/= f (x)». Funktion, die sich selbst - eine starke Lösung, aber Bildung und Verständnis dieser Entscheidung in den meisten Fällen, eine sehr schwierige Aufgabe.

In den alten Zeiten verwendeten die Rekursion für die Vergrößerung des Raums. Durch das System ausgerichtet auf einander spiegeln, können Sie eine atemberaubende dreidimensionale Raumeffekte. Aber es ist einfach zu verstehen, wie passen diese Spiegel? Und noch schwieriger festzustellen, wo sich der Punkt im Raum, reflektierte über mehrere Spiegel.

Rekursion, rekursive algorithmen: die Bedeutung und die Syntax

Die Aufgabe, formuliert die Wiederholung der Sequenz von Operationen kann man rekursiv. Einfacher Algorithmus (Berechnung einer quadratischen Gleichung, Skript füllen Web-Seiten-Informationen, Lesen Sie die Datei, senden einer Mitteilung...) erfordert nicht die Verwendung von Rekursion.

Die Wichtigsten Unterschiede Algorithmus, der erlaubt, die rekursive Lösung:

• Es gibt einen Algorithmus, der muss mehrfach durchgeführt werden;
• Algorithmus braucht Daten, die ändern sich jedesmal;
• Der Algorithmus muss nicht geändert werden jedes mal;
• Eine Letzte Bedingung: der rekursive Algorithmus nicht unendlich ist.

Im Allgemeinen Fall kann man nicht behaupten, dass die einmalige Ausführung - die obligatorische Bedingung der Abwesenheit der Grund für die Rekursion. Man darf auch nicht verlangen obligatorischen endgültigen Bedingungen: bei endlosen rekursionen gibt es eine eigene Anwendungsgebiete.

Mehr:

Das Deutsche Flugzeug "Messerschmitt-262": die Geschichte der Entstehung, Merkmale, Foto

High-Speed-Strahltriebwerk-Kämpfer-Abfangjäger Messerschmitt ME-262 Schwalbe („Messerschmitt ME-262 Schwalbe») erschien auf dem Schlachtfeld nur im Jahr 1944. Man kann nicht genau sagen, für welchen Job diese Maschine bestimmt. Experiment...

Moderne Schule: Geschichte, Voraussetzungen, Probleme. Modelle der modernen Schulen

Historische Entstehung von Schulen förderte den Wunsch der Menschen die Welt zu erkennen und erweitern Ihre Kenntnisse. Deshalb versucht der Mensch zur Gemeinschaft mit den weisen und sehnte sich danach von Ihnen zu lernen wissen.die Geschichte der m...

"Haare zu Berge": Bedeutung, Herkunft фразеологизма

In der Russischen Sprache treffen eine ausreichende Anzahl von geheimnisvollen Floskeln, über deren Bedeutung schwer zu erraten. Die sprachliche Konstruktion „die Haare» gehört eindeutig zu den solchen. Zum Glück, der Ursprung dieses Ausd...

Der rekursive Algorithmus: wenn die Reihenfolge der Operationen wiederholt ausgeführt wird, auf Daten, die ändern sich jedes mal und gibt jedes mal ein neues Ergebnis.

Formel Rekursion

Mathematische Verständnis der Rekursion und Ihre Entsprechung in der Programmierung unterscheiden. Mathematik zwar eigen Zeichen Programmieren, aber die Programmierung ist viel Mathematik höherer Ordnung.

Gut geschriebene Algorithmus - wie ein Spiegel der Intelligenz des Autors. Allgemeine Formel der Rekursion in der Programmierung „f (x)», wo „x ~/= f (x)“ hat mindestens zwei Möglichkeiten der Interpretation. Hier „~» - die ähnlichkeit oder kein Ergebnis, sondern „=” - das Vorhandensein des Ergebnisses der Funktion.

Die Erste Option: die Dynamik der Daten.

• Funktion „f(x)“ hat der Algorithmus eine rekursive und nicht veränderbar;
• „x“ und das „f(x)» - jedes mal haben neue Werte, das Ergebnis der „f(x)” ist eine neue Option „x“ dieser Funktion.

Die Zweite Option: die Dynamik des Codes.

• Die Funktion „f(x)“ hat mehrere algorithmen, raffinierter (Analyse) Daten;
• Datenanalyse - ein Teil des Codes und die Implementierung rekursive algorithmen, die die gewünschte Aktion, - der zweite Teil des Codes;
• Ergebnis der Funktion „f(x)» Nein.

Kein Ergebnis - ein normales Phänomen. Programmieren ist nicht die Mathematik, hier das Ergebnis muss nicht explizit vorhanden sein. Funktion, ausführbares rekursiv, kann nur tun, Parsen von Webseiten und befüllt die Datenbank, oder erstellen Sie das gewünschte Objektinstanzen nach Eingang eingeht Stream.

Daten und Rekursion

Die Programmierung rekursiver algorithmen ist nicht die Berechnung der Fakultät, in dem die Funktion erhält jeder dieses mal, auf gute Einheit in der kleineren oder großen Party - Variante der Realisierung hängt von den Vorlieben des Entwicklers.

Nicht wichtig ist, wie man die Fakultät von „8!» Umzug von 0, 1, 2, ... oder Umgekehrt 8, 7, 6 ... Ähnlich wie die Berechnung einer mathematischen Sequenz, Fraktale oder der unendlichen Reihe aufgezeichnet einfache mathematische Formel, beziehungsweise Algorithmus, der sich strikt an diese Formel.

Verarbeitung von Informationen ist ein „Mathematik» eine völlig andere Ordnung. Rekursive Funktionen und algorithmen hier operieren Buchstaben, Wörtern, Phrasen, Sätzen und Absätzen. Jede nächste Ebene Vorherige verwendet.

Eingabe-Datenstrom analysiert auf einer breiten Palette von Bedingungen, aber der Prozess der Analyse in der Regel рекурсивен. Es macht keinen Sinn, zu schreiben einzigartige algorithmen auf alle Varianten des Eingabestreams. Sollte eine Funktionalität. Hier rekursive algorithmen Beispiele dafür, wie ein Ausgabestream, einen angemessenen Eingang. Es ist nicht das Ergebnis, das auf den Eingang des rekursiven Algorithmus, aber es ist die gewünschte und notwendige Lösung.

Abstraktion, Rekursion und PLO

Die Objektorientierte Programmierung (OOP) und Rekursion - grundsätzlich unterschiedliche Wesen, aber Sie ergänzen sich perfekt. Abstraktion hat keinen Bezug auf die Rekursion, aber durch das PRISMA OOP schafft die Möglichkeit der Implementierung der kontextabhängigen Rekursion.

Zum Beispiel, geht das Parsen von Information und Hervorgehoben Unterschiedliche Buchstaben, Wörter, Sätze, Sätze und Absätze. Es ist offensichtlich, Entwickler liefert die Instanziierung von Objekten dieser fünf Typen und bietet Die Lösung von rekursiven Algorithmus auf jeder Ebene.

In der Zwischenzeit, wenn auf der Ebene der Buchstaben „es macht keinen Sinn, nach der Bedeutung“, dann auf der Ebene der Wörter erscheint Semantik. Unterteilt werden die Worte auf Verben, Substantive, adverbien, Präpositionen ... man Kann weiter gehen und Kasus bestimmen.

Auf der Ebene der Sätze Semantik ergänzt Zeichensetzung und Logik der Kombination von Wörtern. Auf Satzebene nachweisbar genauer Maß an Semantik und Absatz betrachtet werden kann, wie der fertige Gedanke.

Objektorientierte Entwicklung bestimmt die Vererbung von Eigenschaften und Methoden und bietet beginnen die Objekthierarchie mit der Schaffung eines völlig abstrakten Vorfahren. Dabei zweifelsfrei, Analyse jeder Nachkomme wird einen rekursiven Charakter und nicht zu sehr auf der technischen Ebene in vielen Positionen (Buchstaben, Wörter, Phrasen und Sätze). Absätze, die als fertige Gedanken, können sich von dieser Liste, aber nicht das Wesen.

Es ist Wichtig, dass der überwältigende Teil des Algorithmus lässt sich auf der Ebene der abstrakten Vorfahren, die Klärung auf der Ebene der einzelnen Abkömmling Daten und Methoden, die durch mit einer abstrakten Ebene. In diesem Kontext Abstraktion eröffnet neue Horizonte für die Rekursion.

Historische Besonderheiten der OOP

Der PLO kam in die Welt der Programme zweimal, obwohl einige Experten können markieren Sie die Einführung von cloud-Technologien und die modernen Vorstellungen über Objekte und Klassen, wie eine neue Runde in der Entwicklung der IT-Technologien.

Die Begriffe „Objekt“ und „Objekt“ in einem modernen Kontext der PLO, werden als 50-m-und 60-Jahren des letzten Jahrhunderts, sondern assoziieren Sie mit dem Jahr 1965 und die Entstehung von Sprachen Simula, Lisp, Algol, Smalltalk.

In jenen Tagen Unterschied sich nicht Programmieren besonderen Entwicklungen und konnte nicht angemessen auf die revolutionären Konzept. Vor dem Kampf von Ideen und Stilrichtungen der Programmierung (C/C++ und Pascal - meist) noch weit entfernt, und der Datenbank bildeten sich nur noch konzeptionell.

Ende der 80er und Anfang der 90er Jahre in Pascal gab es die Objekte und alle dachten, der Klassen in C/C++ - dies läutete eine neue Runde des Interesses an der PLO und es war dann in der Workbench, vor allem die Programmiersprachen sind nicht nur zu unterstützen objektorientierte Ideen, sondern entwickeln und dementsprechend zu Ihnen.

Natürlich, wenn früher rekursive algorithmen waren eine einfach Funktion, die in der Regel Programmcode, dann ist jetzt die Rekursion konnte ein Teil der Eigenschaften des Objekts (Klasse), was im Kontext der Vererbung bot interessante Möglichkeiten.

Ein besonderes Merkmal der modernen OOP

Die Entwicklung der PLO ursprünglich deklarierten Objekte (Klassen) als Gesamtheit von Daten und die Eigenschaften (Methoden). In der Tat war es über die Daten, die Syntax und Bedeutung. Aber dann nicht vorstellen konnte OOP als Werkzeug für die Verwaltung von realen Objekten.

Die PLO verwandelte sich in ein Werkzeug facility Management „EDV-Natur“. Skript, Schaltfläche, Menüpunkt, die Menüleiste, den Tag in einem Browser-Fenster ist ein Objekt. Aber nicht die Maschine, Nahrungsmittel, Wort oder Satz. Reale Objekte blieben außerhalb der objektorientierten Programmierung und Computer-Tools erworben haben, die neue Inkarnation.

Aufgrund der Unterschiede der gängigen Programmiersprachen, die eine Vielzahl von Dialekten der PLO. Semantik-Sie sind praktisch gleichwertig, und Ihre Orientierung auf eine Kugel, und nicht auf die Anwendung macht es möglich, ertragen die Beschreibung von realen Objekten außerhalb algorithmen und versehen Sie plattformübergreifende und Interkulturelle „Existenz».

Stacks und Mechanismen für den Aufruf der Funktionen

Mechanismen für den Aufruf von Funktionen (Prozeduren, algorithmen erfordern die übertragung von Daten (Parameter), Rückgabe des Ergebnisses und die Speicherung der Adressen-Operator, der die Steuerung nach Beendigung der Funktion (Prozedur).

In der Regel für diesen Zweck verwendet einen Stapel, obwohl die Programmiersprachen selbst oder Fachinformatiker kann vorsehen einer Vielzahl von Optionen, Getriebe-Management. Die moderne Programmierung erlaubt, dass der name der Funktion kann nicht nur eine Option: er kann sich in den Prozess der Ausführung eines Algorithmus. Der Algorithmus kann auch erstellt werden, in den Prozess der Ausführung eines anderen Algorithmus.

Das Konzept der rekursiven algorithmen, wenn Ihre Namen und des Körpers können definiert werden, die im Zeitpunkt der Entstehung der Aufgaben (Auswahl des gewünschten Algorithmus) erweitert рекурсивность nicht nur, wie etwas zu tun, aber wer es genau machen muss. Auswahl des Algorithmus auf seine „sinnvollen» Namen - chancenreich, aber schwierig.

Рекурсивность auf eine Vielzahl von Funktionen

Man kann Nicht sagen, dass der Algorithmus rekursiv, wenn er ruft und sich nur. Programmierung - kein Dogma und das Konzept der рекурсивности ist keine außergewöhnliche Anforderung aufrufen, sich der eigenen Körper-Algorithmus.

Praktische Anwendungen nicht immer eine saubere Lösung geben. Oft die ursprünglichen Daten sollten zu Kochen, und das Ergebnis des rekursiven Aufrufs zu analysieren, im Kontext der gesamten Aufgabe (nur ein Algorithmus) insgesamt.

In der Tat, nicht nur vor dem Aufruf der rekursiven Funktion, sondern auch nach seiner Fertigstellung, kann oder muss ein anderes Programm verursacht werden. Wenn mit einer Herausforderung der besonderen Probleme gibt es: rekursive Funktion A() ruft die Funktion B(), die etwas macht und ruft A(), dann entsteht ein Problem mit der RückgabeVerwaltung. Nachdem er einen rekursiven Aufruf, die Funktion A() soll die Verwaltung, um erneut aufrufen B(), die es wieder auslösen. Return-Management, wie es in der Reihenfolge in den Stapel zurück in B() - falsche Entscheidung.

Programmierer nicht beschränkt in der Wahl der Parameter und kann mit Ihrem Namen Funktionen. Anders gesagt, die ideale Lösung zu vermitteln in A() B name() und lassen Sie selbst A() macht den Aufruf von B(). In dieser Version keine Probleme mit der Rückgabe der Steuerung, und Realisierung des rekursiven Algorithmus wird durchsichtiger.

Das Verständnis und das Niveau der Rekursion

Das Problem der Entwicklung von rekursiven algorithmen ist, dass man eine Vorstellung von der Dynamik des Prozesses. Bei der Verwendung der Rekursion in den Methoden der Objekte, insbesondere auf der Ebene der abstrakten Vorfahren, erscheint das Problem des Verstehens der eigenen Algorithmus im Kontext der Zeit seiner Ausführung.

Derzeit gibt es keine Einschränkungen auf der Ebene der Schachtelung der Funktionen und der Stack-Kapazität in den Mechanismen der Anrufe, aber es gibt das Problem des Verstehens: zu welchem Zeitpunkt auf welcher Ebene welche Art von Daten oder Platz im Allgemeinen Algorithmus führte der Aufruf der rekursiven Funktion und auf welcher Menge Anrufe der es sich befindet.

Vorhandene debugging-Tools oft machtlos Programmierer sagen die richtige Entscheidung.

Schleifen und Rekursion

Es wird Angenommen, dass die zyklische Ausführung der Rekursion entspricht. In der Tat in einigen Fällen, einen rekursiven Algorithmus implementiert werden kann in der Syntax von bedingten und zyklische Strukturen.

Allerdings, wenn es ein klares Verständnis, dass ein bestimmtes Feature umgesetzt werden sollte mittels eines rekursiven Algorithmus, sollten Sie es ablehnen, jeglichen externen Einsatzmöglichkeiten des Zyklus oder bedingte Anweisungen.

Der Sinn hier besteht darin, dass die Lösung in Form einer rekursiven Funktion, die sich selbst erledigt wird, funktional vollständigen Algorithmus. Dieser Algorithmus erfordert vom Programmierer Aufwand bei der Erstellung, das Verständnis der Dynamik des Algorithmus, aber es wird die ultimative Lösung, die nicht erfordert externe Steuerung.

Jede Kombination von externen und zyklischen bedingten Operatoren nicht zulassen, präsentieren einen rekursiven Algorithmus in Form einer vollwertigen fertigen Funktionen.

Konsens Rekursion und der PLO

In Fast allen Fällen die Entwicklung eines rekursiven Algorithmus tritt auf den Plan entwickeln zwei algorithmen. Der erste Algorithmus erzeugt die Liste der zukünftigen Objekte (Instanzen), und der zweite Algorithmus ist eigentlich eine rekursive Funktion.

Die Beste Lösung ist Rekursion zu formalisieren als eine einzelne Eigenschaft (Methode), das eigentlich einen rekursiven Algorithmus, und die ganze Vorarbeit machen den Konstruktor des Objekts.

Rekursive Algorithmus wird nur dann die richtige Lösung, wenn es funktioniert nur selbst, ohne äußere Kontrolle und Verwaltung. Ein externer Algorithmus kann nur geben das Signal zur Arbeit. Das Ergebnis dieser Arbeit sollte die erwartete Lösung, ohne externe Unterstützung.

Rekursion muss stets hochglanzpoliert unabhängige Lösung.

Intuitives Verständnis und funktionale Vollständigkeit

Wenn die objektorientierte Programmierung wurde die de-facto-Standard, wurde deutlich: für die effektive Codierung geändert werden soll das eigene denken. Der Programmierer muss gehen von der Syntax und Semantik der Sprache zur Dynamik der Semantik während der Ausführung des Algorithmus.

Ein Charakteristisches Merkmal der Rekursion: es kann angewendet werden auf der ganzen:

• Parsen von Webseiten;
• Suchaktionen;
• Parsen von Textinformationen;
• Das Lesen oder erstellen von Dokumenten MS Word;
• Extraktion oder Analyse von Tags...

Ein Charakteristisches Merkmal der OOP: es gibt die Möglichkeit, zu beschreiben rekursiven Algorithmus auf der Ebene der abstrakten Vorfahren, aber vorsehen darin einem einzigartigen Appell an die Nachwelt, von denen jeder hat seine eigene Palette von Daten und Eigenschaften.

Rekursion - ideal, denn es erfordert die funktionale Vollständigkeit Ihres Algorithmus. OOP verbessert Qualitätsindikatoren rekursiven Algorithmus, indem Sie ihm den Zugriff auf alle einzigartigen Nachkommen.