Rekursion
aus www.iwiki.de, der freien Wissensdatenbank
Inhaltsverzeichnis |
Definition
Hauptbegriff: Rekursion (recursion)
- Rekursion, auch Rekurrenz oder Rekursivität, bedeutet Selbstbezüglichkeit (von lateinisch recurrere = zurücklaufen). Sie tritt immer dann auf, wenn etwas auf sich selbst verweist. (Quelle: Lexikona)
- Eine Definition ist rekursiv, falls das zu Definierende ganz oder teilweise durch sich selbst definiert wird. (Quelle: Vorlesungsscript)
- Rekursiv heißt eine Funktion, deren Werte derart zusammenhängen, dass sie sich aus einem gegebenen Anfangswert nacheinander durch jeweils die gleiche Formel (Rekursionsformel) berechnen lassen. (Quelle: Brockhaus)
- Für Querdenker:
- Wenn Sie noch nicht begriffen haben, was Rekursion ist, dann bitten Sie einfach jemanden, sich diesen Satz durchzulesen und Ihnen zu erklären, was Rekursion ist! (Quelle: lexikon.martinvogel)
- Um Rekursion zu verstehen, muss man erst einmal Rekursion verstehen. (Quelle: Lexikona)
- Kürzeste Definition für Rekursion: siehe Rekursion . (Quelle: Lexikona)
Weitere Rekursionsbegriffe/-arten
(Vor allem Unterscheidung nach Art und Ort des rekursiven Aufrufs:)
Detailbetrachtung Rekursion
Rekursion ist ein allgemeines Prinzip zur Lösung von (komplexen) Problemen, durch das in der Regel elegante (kürzere) Algorithmen gefunden werden, die aber oft ein schlechteres Laufzeitverhalten aufzeigen als iterative Lösungen.
Grundidee der Rekursion
Die Grundidee dahinter kann mit dem bekannten Slogan „Divide & Conquer“, also „Teile und Herrsche“ beschrieben werden:
- Das Gesamtproblem wird in kleinere Unterprobleme der gleichen Art unterteilt.
- Für kleinste (atomare) Probleme („base cases“) müssen (direkte) Lösungen gefunden werden.
- Die Teillösungen werden zur Gesamtlösung zusammengeführt.
Für die Rekursion heißt das:
- Erster Aufruf der rekursiven Funktion mit maximaler Problemgröße und Gesamtproblem als Parameter.
- Die rekursive Ausführung muss pro Rekursionsschritt die Problemgröße verkleinern.
- Es muss (mind.) einen „base case“ geben, also einen Fall mit direkter Lösung, der auch nach einer endlichen Ausführung von Rekursionsschritten erreicht wird.
So muss jedes (praktikable/berechenbare) Rekursionsschema aus der eigentlichen rekursiven Definition und einem Abbruchkriterium bestehen. Ohne geeignete Abbruchbedingung geraten solche rückbezüglichen Aufrufe in einen so genannten infiniten Regress (Endlosschleife).
Einfaches Beispiel: Potenzieren einer Zahl
Problem: Finde Algorithmus für das Potenzieren einer Zahl: x ⁿ
(der Einfachheit wegen hier nur für positive Exponenten!)
Lösung: Das Gesamtproblem wird in Teilprobleme aufgeteilt und ein „base case“/Abbruchkriterium wird gesucht:
- Bekannt ist das: x° = 1 -> Abbruchkriterium
- Bekannt ist das: x ⁿ+¹ = x ⁿ * x
Also lässt sich ein Algorithmus wie folgt rekursiv darstellen:
int potenz (int x, int n)
{
if( n == 0 )
return (1);
else
return ( potenz (x, n-1) * x );
}
Quellen, frei nach: PII-Script wikipedia uni-hannover phoenix.goucher
Technische Realisierung/Implementierung rekursiver Funktionen
Für jeden Rekursionsschritt (für jeden Aufruf einer rekursiven Funktion) wird ein Rahmen auf dem Stack angelegt. Dieser Rahmen wird mit den aktuellen lokalen Variablen/ Parametern und der Rücksprungadresse gefüllt. Dabei wird eine Art Kette von Rahmen aufgebaut, bis der „base case“ erreicht wird. Wenn ein Funktionsaufruf beendet ist (return…), wird der Rahmen von Stack entfernt, der Rückgabewert abgelegt und die Rücksprungadresse und Parameter des darunter liegenden Rahmens entnommen, um an der über die Adresse referenzierten Programmstelle weiterzurechnen.
Ruft man z.B. die oben definierte Potenzfunktion in der Funktion main() auf...
void main (…)
{
int x = 2;
int n = 2;
System.out.println (potenz (x, n));
}
...werden folgende Werte auf den Stack gelegt:
Stapelanfang-> 1) Platz für Ergebnis 2) Parameter x =2; n = 2 Stapelzeiger-> 3) Rücksprungadresse zu main()
Da n ≠ 0 ist, folgt der Aufruf von potenz (2, 1), dabei werden die aktuellen Werte auf den Stack gelegt:
Stapelanfang-> 1) Platz für Ergebnis 2) Parameter x =2; n = 2 3) Rücksprungadresse zu main() 4) Platz für Ergebnis 5) Parameter x =2; n = 1 Stapelzeiger-> 6) Rücksprungadresse zur Potenz-Funktion
Da n ≠ 0 ist, folgt der Aufruf von potenz (2, 0), dabei werden die aktuellen Werte auf den Stack gelegt:
Stapelanfang -> 1) Platz für Ergebnis 2) Parameter x =2; n = 2 3) Rücksprungadresse zu main() 4) Platz für Ergebnis 5) Parameter x =2; n = 1 6) Rücksprungadresse zur Potenz-Funktion 7) Platz für Ergebnis 8) Parameter x =2; n = 0 Stapelzeiger -> 9) Rücksprungadresse zur Potenz-Funktion
Da jetzt n = 0 ist und dafür das Ergebnis = 1 bekannt ist, werden nach dem Beenden des aktuellen Rekursionsschrittes mit „return(1);“ die Rücksprungadresse zur Potenz-Funktion (siehe Stack-Eintrag Nr. 9) und die Parameter x = 2, n = 0 vom Stack geholt. Das Ergebnis „1“ wird in den Stack auf Platz Nr. 7 eingetragen:
Stapelanfang -> 1) Platz für Ergebnis 2) Parameter x =2; n = 2 3) Rücksprungadresse zu main() 4) Platz für Ergebnis 5) Parameter x =2; n = 1 6) Rücksprungadresse zur Potenz-Funktion Stapelzeiger -> 7) Rückgabewert/Ergebnis = 1
Über die Rücksprungadresse kann die Berechnung an der Stelle: return ( potenz (x, n-1) * x ); wieder aufgenommen werden. Setzt man den Rückgabewert der untersten Rekursionsstufe und den vom Stack geholten, „alten“ Parameter x =2 ein, wird also an dieser Stelle weitergerechnet mit: return ( 1 * 2 ); Nach dem Beenden des aktuellen Rekursionsschrittes mit „return(2);“ wird die Rücksprungadresse zur Potenz-Funktion (siehe Stack-Eintrag Nr. 6) und die Parameter x = 2, n = 1 vom Stack geholt. Das Ergebnis „2“ wird in den Stack auf Platz Nr. 4 eingetragen:
Stapelanfang -> 1) Platz für Ergebnis 2) Parameter x =2; n = 2 3) Rücksprungadresse zu main() Stapelzeiger -> 4) Rückgabewert/Ergebnis = 2
Nun kann in der Potenz-Funktion in der ersten Rekursionsebene weitergerechnet werden: return ( 2 * 2 ); Nach dem Beenden des aktuellen Rekursionsschrittes mit „return(4);“ wird die Rücksprungadresse zur main-Funktion (siehe Stack-Eintrag Nr. 3) und die Parameter x = 2, n = 2 vom Stack geholt. Das Ergebnis „4“ wird in den Stack auf Platz Nr. 1 eingetragen:
Stapelzeiger -> 1) Ergebnis = 4
Über die Rücksprungadresse zur main()-Funktion kann an der Stelle: "System.out.println(4)" weitergerechnet werden.
Quellen, frei nach: wikipedia uni-hannover
Iteration als Alternative für Rekursion
Jede rekursive Lösung lässt sich in eine äquivalente iterative Lösung umformen. Rekursive Lösungen lassen sich zwar gerade bei komplexen Problemen leichter finden, sind aber rechen-und speicherintensiver (Laufzeit wächst exponentiell, Speicherbedarf linear). Rekursive Lösungen können auch als problemnah bezeichnet werden, aufgrund des geringeren Assoziationsaufwandes. Iterative Lösungen sind zwar schneller, dafür aber meist komplexer und schlechter lesbar. Sie können als maschinennah bezeichnet werden. Nicht alle höheren Programmiersprachen lassen rekursive Aufrufe zu; ein Beispiel dazu ist Fortran.
Quellen: wikipedia uni-hannover
Funktionale Programmiersprachen benutzen Rekursion sehr oft als grundlegendes Konzept. Da es in funktionalen Programmiersprachen keine Variablen gibt, die einen Zustand speichern können, ist man hier sehr oft auf eine rekursive Variante angewiesen. Ansonsten müssen, wie im Lisp-Beispiel: Iterative Fakultätsberechnung, alle benötigten Variablen ständig als Parameter übergeben werden. Die Ineffizienz von rekursiven Varianten spielt in funktionalen Programmiersprachen oft keine Rolle, weil hier die Flexibilität mehr gefragt ist. Lisp, ML, Miranda oder Haskell sind Beispiele für funktionale Programmiersprachen. (Quelle: uni-linz)
Beispiel: iterative Lösung des Potenz-Problems
Als Beispiel die Umwandlung der oben behandelten rekursiven Potenz-Funktion in eine iterative Lösung:
int potenzIterativ (int x, int n)
{
int erg = 1;
int basis = x
for (int k = 1 ; k <= n ; k++)
{
erg = basis * erg ;
}
return erg;
}
Anwendungsgebiete für Rekursion
Rekursion und primitiv-rekursive Funktionen spielen eine große Rolle in der theoretischen Informatik, insbesondere in der Komplexitätstheorie und Berechenbarkeitstheorie (siehe Lambda-Kalkül und Ackermann-Funktion).
Im Compilerbau ist der rekursive Abstieg (Recursive Descent) eine Technik, bei der eine Sprache rekursiv geparst wird. wikipedia
Weitere Beispiele zur Rekursion
Türme von Hanoi
Fakultät
Fibonacci-Zahlen
