Rekursion und Iteration

Permutationen

Unter einer Permutation versteht man die Umordnung einer Zeichenfolge. Permutationen der Zeichenfolge 'ABCD' sind beispielsweise 'CBAD' und 'DCBA'. Gesucht ist ein Algorithmus, mit dem man alle Permutationen einer vorgegebenen Zeichenfolge berechnen kann.

Problemlösung

Eine gute Problemlösefähigkeit erreicht man durch fortgesetzte Übung, welche Erfahrung vermittelt, durch Hartnäckigkeit, welche die eigene Leistungsfähigkeit bestätigt, aber auch durch Einsatz typischer Problemlösemethoden: was ist gegeben, was ist gesucht, mache eine Zeichnung, wie kann man das Problem vereinfachen.

Anhand einer Zeichnung erfaßt man die möglichen Permutationen. Ausgehend von ABCD hält man zunächst A fest und bestimmt dann alle Permutationen von BCD. Den Vorgang wiederholt man für alle weiteren Buchstaben, die im Ausgangswort enthalten sind. Alle Permutationen von BCD erhält man nach dem gleichen Schema. Man hält B fest und bildet alle Permutationen von CD, dann hält man C fest und bildet alle Permutationen von BD, zuletzt hält man D fest und bildet alle Permutationen von BC.

Im Algorithmus muss also unterschieden werden, was festzuhalten und was noch zu permutieren ist. Insgesamt gesehen werden die Permutationen von vier Zeichen durch vier Permutationen zu je drei Zeichen bestimmt, wodurch die rekursive Struktur des Lösungsalgorithmus gegeben ist.

Zur Programmierung einige Hinweise: für den Zugriff auf das i-te Zeichen des Strings Eingabe benutzt man ähnlich wie bei einem Feldzugriff die Schreibweise Eingabe[i]. Mit der Prozedur Delete können ein oder mehrere Zeichen in Strings gelöscht werden. Einzelheiten erfährt man in der Hilfe. Man kann auch gut mit der Copy-Funktion arbeiten.

Übung

a) Programmiere den Algorithmus Permutiere.
b) Bestimme seine Komplexität.

Fibonacci-Zahlen

Die Zahlen der Folge 0, 1, 1, 2, 3, 5, 8, 13, 21,... bezeichnet man als Fibonacci-Zahlen. Das Bildungsgesetz lautet fib(n) = fib(n-1) + fib(n-2) mit den beiden Anfangswerten fib(0) = 0 und fib(1) = 1. Das Bildungsgesetz hat eine rekursive Struktur, weswegen man leicht eine rekursive Funktion zur Berechnung von Fibonacci-Zahlen programmieren kann.

  1. Bis zu welchem n berechnet die rekursive Funktion fib(n) in erträglicher Zeit?
  2. Vergleiche mit einer iterativen Lösung.

Aufrufdiagramm

Stellt man jeden Aufruf der fib-Funktion als Rechteck dar, so erhält man das nebenstehende Aufrufdiagramm. Über den rechtsgerichteten Pfeilen steht jeweils das Argument, mit dem fib aufgerufen wird. Die linksgerichteten Pfeile zeigen die Ergebnisse an.

Das Aufrufdiagramm macht deutlich, dass Rekursion Wiederholung durch Schachtelung ist.

Die Komplexität des Berechnungsalgorithmus wird letztlich durch die rekursiven Aufrufe bestimmt. In der nachfolgenden Tabelle sind in Abhängigkeit von n die Fibonacci-Zahlen und die Zahl der zwecks Berechnung erforderlichen fib-Aufrufe dargestellt. Man sieht, daß die Zahl der Aufrufe noch stärker wächst als die Fibonacci-Zahlen.

Aufruf-Tabelle

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Fib(n) 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
Aufrufe(n) 1 1 3 5 9 15 25 41 67 109 177 287 465 753 1219 1973
 

Die Mathematik liefert für die Fibonacci-Zahlen die Formel: Sie macht deutlich, dass der Berechnungsalgorithmus exponentielle Komplexität hat. Lineare Zeitkomplexität erhält man durch die folgende iterative Lösung, konstante Zeitkomplexität durch Anwendung der Formel. 

function fib(n: Integer): Real;
  Var i, Fib0, Fib1, FibN: Integer;
begin
  If n = 0 then FibN:= 0 else FibN:= 1;
  Fib0:= 0; Fib1:= 1;
  for i:= 2 to n do begin
    FibN:= Fib0 +  Fib1;
    Fib0:= Fib1;
    Fib1:= FibN;
  end;
  Result:= FibN;
end;

Zusammenfassung

Rekursion ist Wiederholung durch Schachtelung.
Iteration ist Wiederholung durch Aneinanderreihung.

Rekursion versus Iteration
Es stellt sich die Frage, wann man ein Problem iterativ oder rekursiv lösen sollte. Als Richtschnur kann dabei gelten, dass Rekursion angewendet werden sollte, wenn

Falls das zugrundeliegende Problem die entsprechende Struktur hat, sind rekursive Lösungen oft besser lesbar und eleganter, aber, wie gezeigt, nicht unbedingt effektiver. Eine rekursive Problemlösung sollte immer dann vermieden werden, wenn eine iterative Lösung offensichtlich ist.

Übungen

  1. Der größte gemeinsame Teiler (ggT) zweier ganzer nicht negativer Zahlen m und n kann nach dem griechischen Mathematiker Euklid wie folgt definiert werden:

    für m = n: ggT(m, n) = m
    für m < n: ggT(m, n) = ggT(n, m) //n und m werden vertauscht
    für m > n > 0: ggT(m, n) = ggT(n, m mod n)
    für m > n = 0: ggT(m, n) = m

    Dabei ist mod der in Pascal vorhandene Modulo-Operator. m mod n ergibt den Rest bei der ganzzahligen Divison von m durch n.
    a) Schreibe gemäß Euklid eine rekursive Funktion zur Berechnung des ggT.
    b) Entwickle auch eine iterative Lösung.
     
  2. Die Anzahl der Permutationen von n Zeichen beträgt
    a) in rekursiver Formulierung: n! = n*(n-1)! mit 1! = 1 (n! = n-Fakultät)
    b) in iterativer Formulierung: n! = n*(n-1)*(n-2)...*3*2*1
    Gib jeweils eine rekursive und iterative Funktion zur Berechnung von n! an.
     
  3. Gesucht sind alle Möglichkeiten, nach denen ein Faden der ganzzahligen Länge n unter Beachtung der Reihenfolge in Teile der Länge 1 oder 2 zerschnitten werden kann.
     
  4. Der Turm von Hanoi
    Nach einer alten Legende befanden sich vor einem Tempel in Hanoi drei Säulen. Auf der ersten Säule befanden sich hundert Lochscheiben, deren Durchmesser von unten nach oben abnahm. Es bestand eine Weissagung, dass die Welt untergehen würde, wenn es jemandem gelänge, den Turm unter Beachtung der folgenden Regeln auf eine der anderen Säulen umzubauen:
    1. Man darf jeweils nur eine einzelne Scheibe umlegen.
    2. Nur die oberste Scheibe einer Säule darf bewegt werden.
    3. Es ist verboten, eine Lochscheibe mit größerem Durchmesser auf eine Lochscheibe mit kleinerem Durchmesser zu legen.
    a) Finde eine Algorithmusidee, indem du eine Säule aus zwei, drei, vier Scheiben selbst konkret umbaust, z.B. mit Münzen.
    b) Erstelle hierzu ein Simulationsprogramm, das ausgibt, von wo nach wo gerade eine Scheibe umgelegt wird.