Programmierkurs: Delphi: Pascal: Rekursion
Aus Wikibooks
Inhaltsverzeichnis |
[Bearbeiten] Rekursion
[Bearbeiten] Definition
Als Rekursion bezeichnet man das Verfahren, dass eine Funktion ihren Rückgabewert durch Aufruf von sich selbst berechnet. Für viele Probleme existiert neben einer rekursiven Lösung auch eine iterative Lösung (Lösung durch Anwendung einer Schleife). Zudem müssen genügend Startwerte existieren (im Beispiel unten 0 für n=0).
[Bearbeiten] Beispiele für Rekursionen
Ein bekanntes Beispiel für ein Problem, das meistens (und sinnvollerweise) durch Rekursion gelöst wird, sind die 
Türme von Hanoi, ein mathematisches Spiel. Prinzipiell lässt sich dieses Problem auch iterativ lösen. Ein anderes sinnvolles Beispiel ist Floodfill, ein Algorithmus zum Einfärben von benachbarten Pixel gleicher Farbe.
[Bearbeiten] Beispiel einer Rekursionsprozedur
function Quersumme(n: Integer): Integer; begin if n = 0 then Result := 0 else Result := (n mod 10) + Quersumme(n div 10); end;
[Bearbeiten] Rekursive und iterative Programmierung im Vergleich
Rekursive Algorithmen sind oft kürzer als iterative, leichter zu verstehen und gelten als eleganter. Iteration ist dafür ressourcensparender und schneller, weil der wiederholte Funktionsaufruf entfällt. Im Extremfall kann es bei der Rekursion zum Stapelüberlauf kommen, wenn der Stapelspeicher nicht mehr ausreicht. Zudem sind in iterativen Lösungen Fehler leichter zu finden. Daher ist die iterative Vorgehensweise der rekursiven immer vorzuziehen, wenn es eine Iterative Lösung gibt (und sich diese auch in vernünftiger Zeit finden lässt). Beispielsweise sollte Rekursion nicht zur Berechnung von Fakultät, Summen, der Fibonacci-Zahlen und ähnlichem Verwendung finden.
[Bearbeiten] Links
Wikipedia Artikel zu rekursiver Programmierung: Rekursive Programmierung
 Pascal: Methodenzeiger |
Inhaltsverzeichnis | Pascal: Klassen  |
