Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Freitag, 24. März 2017 09:03 
Rekursion in der praktischen Informatik
 
Geschrieben von alexander am Montag, 13. Februar 2006

Das Ziel dieses Artikels besteht darin, die Rekursion als praktisch verwertbare Methode der Programmierung zu untersuchen. Insbesondere werden Themen wie Primitiv-Rekursion o.ä. in diesem Artikel nicht behandelt - dies sei der theoretischen Informatik vorbehalten. In diesem Dokument wollen wir das Zeichen stets als die natürlichen Zahlen (inklusive der 0) verstehen.

Die Rekursion ist ein fundamentales Prinzip in der Mathematik und Informatik:
In der Mathematik spricht man von der rekursiven Definition einer Funktion, wenn diese „durch sich selbst definiert wird“. Eines der bekanntesten Beispiele der Mathematik ist die Fibonacci-Folge: Es sei f: eine Funktion (genauer eine Folge) definiert durch

  • f(0) := 1
  • f(1) := 1
  • f(n) := f(n-1) + f(n-2) [für n>1]
Es ist also f(2) = f(2-1) + f(2-2) = f(1) + f(0) = 2. Das (n+1)-te Folgenglied ergibt sich also stets durch Addition des n-ten und des (n-1)-ten Folgengliedes. Die ersten Folgenglieder sind also {1, 1, 2, 3, 5, 8, 13, 21, 34, ...}.
Auch in der Mathematik ist das wesentliche der Rekursion die Möglichkeit, eine unendliche Menge von Objekten durch eine endliche Aussage zu definieren. Auf die gleiche Art kann eine unendliche Zahl von Berechnungen durch ein endilches rekursives Programm beschrieben werden, ohne dass das Programm explizit Schleifen enthält. Natürlich können nur endlich viele Berechnungen auf Rechenmaschinen durchgeführt werden, doch zumind. die Beschreibung ist in diesem Sinne vollständig.


In der Informatik ruft eine rekursive Prozedur (oder Funktion -im Folgenden gleichgedeutend) sich selbst auf. Da eine rekursive Prozedur sich nicht unendlich oft aufrufen (infiniter Regress, Endlosschleife) darf, wenn das Programm terminieren soll, muss nach endlich vielen Aufrufen eine Situation erreicht werden, in der kein rekursiver Aufruf mehr erfolgt. Daher muss sich eine rekursive Prozedur für immer kleiner werdende Teilprobleme aufrufen, bis diese schließlich so klein sind, daß ihre Lösung trivial ist.
Oftmals sind rekursive Problemlösungen grundsätzlich dort angebracht, wo das Problem, die Funktion oder die Datenstruktur bereits rekursiv definiert sind. Grundsätzlich bedeutet jedoch stets das Ausnahmen existieren:
Die Fakultätsfunktion n!:

  • f(0) := 1
  • n! := n(n-1) [für n>0]
ist zwar eine typische Vertreterin der rekursiven Funktionen, doch wäre eine rekursive Implementierung mitnichten sinnvoll!

Das Prinzip der Rekursion ist eng mit dem 'Divide and Conquer'-Paradigma verwandt.

Eine rekursives Programm setzt sich i.d.R. aus der rekursiven Prozedur, den rekursiven Aufrufen und den sonstigen Anweisungen zusammen. Dabei sind die rekursiven Prozeduren wie folgt zu charakterisieren:

  • Der Rückgabewert eines rekursiven Prozeduraufrufes ergibt sich durch Verknüpfung bereits vorher berechneter Rückgabewerte.
  • Die (endlich vielen) rekursiven Prozeduraufrufe sollten dem Zwecke der Problemreduktion dienen.
  • Damit kein infiniter Regress, also eine Endlosschleife entsteht, muss eine passende Abbruchbedingung die rekursiven Aufrufe genau dann stoppen, wenn die Lösung des gestellten Problems trivial ist.

Unter Praktikern hat die Rekursion oftmals einen schlechten Ruf, da sie für ineffizient bzgl. Laufzeit- und Speicherplatzbedarf gehalten wird. Dieser Eindruck entsteht vor allem dadurch, daß die Rekursion vielfach für ungeeignete Anwendungen eingesetzt wird.

Eine sinnvoll angewandte rekursive Prozedur ist - insbesondere bei der heutigen Rechnerarchitektur - vergleichbar effizient wie eine nichtrekursive, d.h. iterative Prozedur. Dagegen ist eine rekursive Lösung bzgl. der Programmkomplexität häufig erheblich einfacher, d.h. hat z.B. weniger Fallunterscheidungen, einfachere Abbruchbedingungen von Schleifen und kann oftmals auf Hilfsdatenstrukturen verzichten, die eine iterative Prozedur benötigt.
Eine rekursive Lösung ist einer iterativen Lösung also stets dann vorzuziehen, wenn für die iterative Lösung eine zusätzliche Hilfsdatenstruktur benötigt würde.
Nun ist auch klar, warum es sinnvoller ist, die Fakultätsfunktion iterativ zu implementieren - die nicht-rekursive Lösung benötigt keine zusätzliche Hilfsdatenstruktur im Vergleich zur Rekursiven.
Im Folgenden wird der Typ einer Variablen unmittelbar durch den Anhang ':Typ' an den Bezeichner charakterisiert. Ferner werden in den eckigen Klammern [...] Kommentare innerhalb des Pseudocodes notiert.

Prozedur FakultätRekursiv (Argument, Fakultät:):

Wenn Argument = 0 dann{
[Problemlösung trivial!, Abbruchbedingung]
Fakultät:=1
}
sonst{
[Problemreduktion durch Subtraktion:]
Fakultät:= Argument * FakultätRek(Argument - 1)
}
Ausgabe Fakultät

Es scheint zunächst erstaunlich, wie diese Prozedur die Fakultät einer beliebigen natürlichen Zahl berechnen soll.
Es ist unbedingt zu beachten, dass der erste Prozedurdurchlauf erst am Ende der Berechnung vollendet wird!
Machen wir uns die Funktionsweise dieser Prozedur bewußt. Jeder Durchlauf der Prozedur beginnt mit einer bedingten Anweisung (meist in Form einer if-then-else-Anweisung), hier wird überprüft, ob das Argument gleich 0 und damit die Lösung des Problems trivial ist. In diesem Fall steht die Antwort nach Definition (der Fakultät) bereit fest, dieser Fall stellt also das Abbruchkriterium dar.
Anderenfalls wird versucht der Ausgabe-Variablen Fakultät ein Wert durch eine Multiplikation zuzuweisen. Ein Faktor der Multplikation ist (noch) unbestimmt, da dieser in Form eines Selbstaufrufes der Prodzedur FakultätRek. Der wesentliche Unterschied zum ersten initiierendem Aufruf ist, dass das übergebene Argument, also die Zahl für welche die Fakultät berechnet werden soll, um den Subtrahenden 1 reduziert wird.

Durch diesen Selbstaufruf beginnt das Spiel von neuem, solange bis das Argument durch die rekursiven (Selbst-)Aufrufe bis auf 0 reduziert wurde. In diesem Fall ist die Problemlösung, wie bereits erwähnt, trivial. Erst jetzt wird die Zuweisung Fakultät:=1 durchgeführt, und an die noch laufenden Prozeduren zurückgegeben.

Jede Rekursion kann mit Hilfe einer geeigneten Hilfsdatenstruktur, meist in zusammengesetzter Form, substituiert werden. Umgekehrt kann jede Iteration (insb. also Schleifen) durch rekursive Prozeduraufrufe ersetzt werden.

Würde man die rekursiven Aufrufe visualisieren wollen, so würde sich dann u.U. ein rekursiver Baum abzeichnen. Ein Beispiel finden Sie auf der Übersichtsseite Informatik.

Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.074 Sekunden, mit 54 Datenbank-Abfragen