Home » Tutorials » Programmierkonzepte » Rekursive Algorithmen

Rekursive Algorithmen

Iteration

Neben der Rekursion steht die Iteration als gleichwertiges Verfahren zur Problemlösung bereit. Was es damit auf sich hat, soll dieser Schritt klären.
Jetzt wollen wir uns nochmals an den Anfang erinnern. Dort war von der Bottom-Up-Methode die Rede gewesen. In diesem Zusammenhang habe ich behauptet, dass wir „in einem späteren Schritt den Zusammenhang dieser Methode mit einem Verfahren, das iterativ arbeitet, erkennen können.“
Gleich muss ich den Beweis dazu antreten.
Wenn die rekursive Problemlösung doch etwas so Tolles ist, wie ich eben behauptet habe, hat sie aber bei alledem auch Nachteile. Nicht jeder rekursive Algorithmus muss auch rekursiv programmiert werden. Das alternative Verfahren zur Rekursion ist die Iteration, die Berechnung durch wiederholtes Anwenden einer Operation in einer Schleife. Und da sind wir wieder der Bottom-Up-Methode sehr nahe.
Zunächst eine kleine Spielerei mit Buchstaben und Wörtern.
Wie viel verschiedene Wörter kann man aus den vier Buchstaben A, M, O, R bilden?

Lösung:

AMOR AMRO AOMR AORM ARMO AROM
MAOR MARO MOAR MORA MRAO MROA
OAMR OARM OMAR OMRA ORAM ORMA
RAMO RAOM RMAO RMOA ROAM ROMA

Zuerst gibt es vier Möglichkeiten, den ersten Buchstaben zu wählen. Ist dieser gewählt, so gibt es nur noch drei Möglichkeiten, den zweiten Buchstaben zu wählen. Für den dritten Buchstaben sind noch zwei Möglichkeiten vorhanden und nur noch eine für den letzten Buchstaben.
Da die Wahlmöglichkeiten unabhängig voneinander sind, gibt es insgesamt
4 * 3 * 2 * 1 = 24 Möglichkeiten.
In der Mathematik – Du weißt es – nennt man das Produkt 4 * 3 * 2 * 1 auch „Fakultät von 4“ und schreibt dafür 4! (vier Fakultät).
So ist beispielsweise:

1! = 1 3! = 3 * 2 * 1 5! = 5 * 4 * 3 * 2 * 1
2! = 2 * 1 4! = 4 * 3 * 2 * 1 n! = n * (n-1) * (n-2) * … * 1

Daraus folgt die allgemeine rekursive Definition für n! :

Definition für n-Fakultät:

Für n > 1 gilt n! = n * (n-1)!

Für n = 1 gilt n! = 1
Du siehst:
n! wurde mit einer einfacheren Variante von sich selbst, nämlich mit (n-1)! definiert. Also 5! durch 5*4! und dann 4! durch 4 * 3! usw. bis wir bei 1! = 1 angekommen sind. Dann muss die Rekursion wegen der Bedingung n > 1 abbrechen.
Wir setzen diese Definition in die folgende Funktion um:

function fakrek (n: Integer): LongInt;
begin
  if n > 1 {die Abbruchbedingung} then
    Result := n * fakrek (n-1)
  else
    Result := 1;
end; {der Funktion fakrek}

Da der Funktionswert schnell sehr groß werden kann, verwenden wir für das Funktionsergebnis den Wert LongInt (-2147483648..2147483647 / 32 Bit einschließlich Vorzeichen). Trotzdem liefert die Funktion für n > 12 falsche Ergebnisse, da für n > 12 auch der Wertebereich von LongInt überschritten wird.
Die Funktion kannst Du im Programm fak1.exe (in der Datei TutExe.exe) ausprobieren. Dort gibt es auch den Quelltext (ufak1.pas).
Obwohl die mathematische Definition von n! rekursiv ist – wie wir eben festgestellt haben -, können wir mit Hilfe einer einfachen FOR-Schleife die Rekursion vermeiden.
Die Funktion dazu kommt hier:

function fakitera (n: Integer): LongInt;
var I: Integer;
    F: LongInt;
begin
  F := 1;
  for I := 2 to n do F := F * I;
  Result := F;
end; {der Funktion FakItera}

Bei der Berechnung von n! gehen wir jetzt, getreu der Bottom-Up-Methode, vom einfachsten zum komplizierteren. Deshalb beginnen wir in der Funktion fakitera mit F := 1. Für alle natürlichen Zahlen i von 2 bis n wird der neue Wert von F jeweils aus dem alten Wert von F durch die Anweisung F := F * I berechnet. Die Anweisung F := F * I wird also (n-1)-mal nacheinander ausgeführt.
Eine kurze Zusammenfassung:
Das in Funktion fakitera angewandte Verfahren ist nicht rekursiv sondern iterativ. Im Gegensatz zur Rekursion beginnt man bei der Iteration mit der einfachsten Stufe und berechnet in einer Schleife aus der vorangegangenen Stufe die nächsthöhere, solange bis das Ziel erreicht ist.
Natürlich muss auch jeder iterative Algorithmus und jede iterative Prozedur oder Funktion eine Abbruchbedingung haben, die auch erreicht wird.
Bei der Iteration wird der Rekursionsschritt umgekehrt. Während man bei der Rekursion von einer Stufe zu einer einfacheren Stufe zurückgeht (Rekursionsschritt), geht man bei der Iteration von einer Stufe zur nächsthöheren (Iterationsschritt), um dann die nächstkompliziertere Iterationsstufe zu erreichen.
Bei der rekursiven Berechnung von n! realisiert die Anweisung

Fak := N * Fak(n-1)

den Rekursionsschritt.
Bei der iterativen Berechnung von n! realisiert die Anweisung

Fak := Fak * n

den Iterationsschritt.
Unter ufak1.pas und ufak2.pas kannst Du beide Programmierverfahren nochmals miteinander vergleichen.
Der italienische Mathematiker Leonardo Fibonacci (um 1170 bis ca. 1240), der das mathematische Wissen des klassischen europäischen, arabischen und indischen Kulturkreises zusammentrug und durch Beiträge zur Algebra und Zahlentheorie ergänzte, hat eine Zahlenreihe in der folgenden Form, die sogenannte Fibonacci-Reihe, entwickelt, die in der Mathematik weit verbreitet ist:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55 usw.
Wer gern knobelt, kann ja in der Zwischenzeit überlegen, welchem mathematischen Gesetz diese Zahlenreihe folgt. Wenn Du keine Lust dazu hast – auch nicht schlimm. Du erfährst es sowieso gleich.
Das Geheimnis dieser Zahlenreihe beruht auf der Tatsache, dass eine Zahl in dieser Reihe stets die Addition der beiden vorhergehenden Zahlen ist; dabei sind die erste und die zweite Zahl der Reihe jeweils mit dem Wert 1 belegt.
Anhand dieser Zahlenreihe könnten wir Rekursion und Iteration auf interessante Weise miteinander vergleichen und die Unterschiede zwischen beiden Programmiertechniken deutlich herausstellen. Aber da das auch wieder nur eine Sache für Interessierte ist und Du sicher nochmals eine Verschnaufpause brauchst, will ich für alle, die Interesse an diesem Vergleich haben, noch ein Programm zur Verfügung stellen, das uns den Unterschied in der Verarbeitungsdauer verdeutlichen kann (Beispieldatei: uFibona.pas).
In der Informatik gilt ein bewiesener Satz, so habe ich gelesen, dass es zu einer rekursiven Problemlösung immer auch eine iterative gibt.
Theoretisch könnten wir nach diesem Satz auf die rekursive Lösung ganz verzichten. Doch das ist wirklich nur Theorie. Man muss nämlich erst einmal für eine bestimmte Klasse von Problemen einen iterativen Algorithmus finden. So ist zum Beispiel für das Problem der „Türme von Hanoi“ eine iterative Lösung grundsätzlich möglich, jedoch außerordentlich schwierig. Mir ist nicht bekannt, dass es so eine Lösung gibt.
Wegen der nur angerissenen möglichen Nachteile der Rekursion sollte sie immer dann vermieden werden, wenn eine iterative Lösung offensichtlich ist. Lässt sich dagegen ein rekursiver Algorithmus leichter finden und elegant formulieren und spielt die Rechenzeit keine Rolle, so ist die Rekursion vorzuziehen.
Ein interessantes Beispiel für Rekursion wäre auch ein Sortieralgorithmus nach dem Grundsatz „Sortieren durch Mischen (MergeSort)“.
Nach dem Prinzip von „Teile und Herrsche“ erhält man einfachere Varianten eines zu sortierenden Feldes, indem man es in ungefähr gleiche Teile aufteilt, jede Hälfte getrennt sortiert und dann die Hälften zusammenmischt.
Mit diesem Ansatz lässt sich ein Rekursionsschritt wie folgt skizzieren:

  • Sortiere die erste Hälfte des Feldes
  • Sortiere die zweite Hälfte des Feldes
  • Mische beide Hälften zusammen.

Die Programmierung dieses Beispiels überlasse ich Dir, wenn Du das willst. Die Richtung habe ich ja angegeben.
Übrigens: Es gibt Probleme, für die sich ein Lösungsalgorithmus nicht direkt angeben lässt. Sofern es überhaupt eine Lösung gibt, kann man sie höchstens durch systematisches Ausprobieren finden. In der Informatik spricht man von Backtracking-Verfahren.
Auch bei diesem Programmierverfahren, das einen Zugang zu einer ganz neuen Klasse von Problemlösungsmethoden liefert, spielt die Rekursion eine wichtige Rolle.
Darüber vielleicht einmal später.