WikiDer > Rekursion (Informatik)

Rekursion in die Informatik und Computer Engineering ist eine Methode, bei der die Lösung eines Problems von Lösungen kleinerer identischer Probleme abhängt, im Gegensatz zu Wiederholung.^[1]

Dieser Ansatz kann auf viele Arten von Problemen angewendet werden und Rekursion ist eine Grundlage der Informationstechnologie.^[2] Rekursion ist in Mathematik und Informatik üblich. Zum Beispiel können Operationen auf Zahlen als beliebig große Kombinationen von Zahlen und Operationen wie Addition, Subtraktion, Multiplikation und Division geschrieben werden. Viele mathematische Formalismen und Computersprachen werden daher mit rekursiven Grammatikist beschrieben.

Datenverarbeitung

Eine andere Form der Rekursion auf Speziesebene ist die rekursive Datenstruktur: Enthält einen oder mehrere Elementtypen, die direkt oder indirekt auf Elemente desselben Typs verweisen.

Ein Beispiel, bei dem die Rekursion nur auf Artebene stattfindet, ist die Baum: das besteht aus Knoten deren Zweige selbst Bäume sind, aber ein Baum kann nicht Teil seiner eigenen Zweige sein.

Außerdem werden häufig echte rekursive Datenstrukturen verwendet. Dies ist zum Beispiel der Fall, wenn a gerichteter Graph ist definiert als eine Menge von Knoten mit einer Liste von Nachfolgeknoten für jeden Knoten: In einem Graphen kann ein Knoten direkt oder indirekt sein eigener Nachfolger sein.

Zusätzlich zur Datenrekursion wird Rekursion häufig in Berechnungen verwendet, indem sie als rekursive Funktion definiert wird: eine Funktion, die sich selbst aufruft. In der Arithmetik ist dies eine sehr verbreitete und alte Idee; es ist ein beispiel Euklids Algorithmus zur Bestimmung der größter gemeinsamer Teiler von zwei ganzen Zahlen.

Rekursive Funktionen werden normalerweise verwendet, um Operationen an rekursiven Datenstrukturen zu beschreiben.

Beispielsweise können in dem gegebenen Beispiel aber auch die direkten Untergebenen eines Mitarbeiters an den indirekten Untergebenen interessiert sein. Die direkten Untergebenen von Peter lassen sich in einem Schritt ermitteln: Das sind diejenigen, die als boss_id (Jan und Roel) den Wert "2" (Peters Mitarbeiter_id) haben. Um auch alle Untergebenen von Peter zu finden, muss der gleiche Vorgang wiederholt werden. Zuerst die Untergebenen von Jan und Roel finden. Für Jan sind das Gert und Harry. Roel hat keine Untergebenen. Der nächste Schritt besteht darin, die Untergebenen von Gert und Harry zu finden und so weiter und so weiter, bis keine Untergebenen mehr gefunden werden. Dieses „Auslaufen einer Beziehung, bis alles gefunden ist“ ist in der Praxis weit verbreitet. Dafür gibt es einen mathematischen Begriff: Die Relation "indirekt untergeordnet" ist die Transitive Schließung des "direkten untergeordneten" Verhältnisses.

Das Nachschlagen aller Untergebenen geschieht am besten mit einer rekursiven Funktion, da der Vorgang jedes Mal identisch ist, nämlich: "Finde die IDs aller Mitarbeiter mit Nummer" nein als Chef", wobei das Ergebnis die Eingabe des nächsten Aufrufs der Funktion ist. Es ist nicht sofort klar, wie oft die Funktion wiederholt werden soll. Es ist klar, wann die Funktion "fertig" ist, nämlich ob die neu gefundenen Untergebenen selbst keine Untergebenen mehr haben.

Es ist natürlich wichtig, dass sich die Funktion irgendwann nicht mehr selbst aufruft, sonst läuft der Prozess auf unbestimmte Zeit weiter. Im obigen Beispiel ruft sich die Funktion nicht selbst auf, wenn keine neuen Untergebenen gefunden werden. Es können auch Vorbedingungen formuliert werden, wie z. B. wie oft sich eine Funktion maximal selbst aufrufen darf.

Eine ähnliche Baumstruktur bilden die Ordner und Dateien auf einem Computer. Jeder Ordner kann (neben Dateien) auch einen Ordner selbst enthalten. Um alle Dateien in einem Ordner und allen Unterordnern zu finden, a rekursiv Prozess benötigt.

Wenn dazu auch symbolische Links gehören oder Verknüpfungen befolgt werden, handelt es sich nicht mehr immer um einen Baum: Es kann Fahrräder existieren. Um in einem solchen Fall eine endlose Fortsetzung des Prozesses zu verhindern, kann während des Laufs beispielsweise überprüft werden, ob ein erreichtes Element noch nicht erreicht wurde,

Fraktale werden durch eine rekursive Funktion gebildet: auf a komplexe Zahl eine Berechnung wird freigegeben. Das Ergebnis ist eine neue komplexe Zahl, die die Eingabe für den nächsten Aufruf derselben Funktion ist. Die computergenerierten Bilder werden erzeugt, indem die komplexen Zahlen in einem Koordinatensystem aufgetragen werden und die Farbe jedes Punktes durch das Endergebnis nach einer vorbestimmten Anzahl von Aufrufen bestimmt wird.

Andere Informatikanwendungen, die Rekursion verwenden, sind: Sortieralgorithmen und der Fourier-Analyse.

Nachteile

Rekursion ist oft ein natürlicher und eleganter Weg, um Funktionen oder Prozeduren zu definieren. Bei einer tatsächlichen Implementierung muss man jedoch vorsichtig damit sein. Während die Rekursion manchmal schnell und effizient funktioniert (wie beim Sortieralgorithmus Schnelle Sorte), ist es auch oft viel langsamer als nicht-rekursive Implementierungen. Für jede rekursive Funktionsaufruf ist eine Zahl Taktzyklen notwendig und auch jedes Mal eine Reihe von registriert auf der Aufrufliste platziert werden. Eine einfache für Schleife arbeitet schneller und verbraucht weniger Speicher. Viele Compiler können jedoch Rekursionen erkennen und so übersetzen, dass sie in der ausführbaren Datei nicht mehr vorhanden sind. Compiler für funktionale Programmiersprachen wenn lispeln und Haskell, zum Beispiel Formen Schwanz rekursiv Funktionen werden oft automatisch in äquivalente nicht-rekursive Funktionen umgewandelt.

Formen der Rekursion

Wenn eine Funktion in einem Programm mit einem Aufruf an sich selbst endet, wird dies als "Tail-Rekursion" bezeichnet. Wenn sich zwei Funktionen gegenseitig aufrufen, wird dies als 'reziproke Rekursion' bezeichnet.

Fußnoten