Programmierkurs: Delphi: Pascal: Rekursion

Rekursion

Als Rekursion bezeichnet man das Verfahren, dass eine Funktion ihren Rückgabewert durch Aufruf von sich selbst berechnet. Dabei muss die Funktion mindestens einen Startwert entgegennehmen und diesen in jedem Durchgang wieder neu berechnen. Damit dies kein endloser Vorgang wird, muss weiterhin sichergestellt sein, dass die Rekursion bei Erreichen eines festgelegten Startwertes oder Ergebnisses innerhalb der Berechnung endet.

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 Pixeln gleicher Farbe.

Beispiel einer Rekursionsfunktion

function Quersumme(n: Integer): Integer;
begin
  if n = 0 then
    Result := 0
  else
    Result := (n mod 10) + Quersumme(n div 10);
end;

Das Programm trennt bei jedem Durchgang die letzte Ziffer ab und addiert diese zur Quersumme der übrigen Ziffern. Wenn keine Ziffern mehr übrig sind (Startwert n = 0), endet die Rekursion.

Um den Ablauf dieses Beispiels zu verstehen, seien hier einmal die Schritte beim Aufruf mit dem Startwert 713 erklärt.

• 1. Aufruf: 713 <> 0, also 3 + Quersumme(71)
• 2. Aufruf: 71 <> 0, also 1 + Quersumme(7)
• 3. Aufruf: 7 <> 0, also 7 + Quersumme(0)
• 4. Aufruf: 0 = 0, Rückgabe von 0 an den 3. Aufruf
• 3. Aufruf: Rückgabe von 7 + 0 = 7 an den 2. Aufruf
• 2. Aufruf: Rückgabe von 1 + 7 = 8 an den 1. Aufruf
• 1. Aufruf: Rückgabe von 3 + 8 = 11 an das Hauptprogramm
• Ergebnis: Quersumme(713) = 11

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. Wie man im obigen Beispiel sieht, bleiben alle Aufrufe im Speicher, bis die Rückgabewerte rückwärts wieder verarbeitet werden können. Im Extremfall kann es bei der Rekursion daher 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.

Links

Wikipedia-Artikel zu rekursiver Programmierung: http://de.wikipedia.org/wiki/Rekursive_Programmierung

Pascal: Prozedurale Typen

Inhaltsverzeichnis

Pascal: Klassen