Skript zu: Einfuehrung in die Informatik I: Rekursion und Iteration (1)

Rekursion und Iteration (1)

Bei der rekursiven Zerlegung eines Problems in kleinere Teilprobleme tritt ein Sonderfall häufig auf (leider nicht oft genug), den wir rechtsrekursiv nennen, und der sich in eine effiziente nichtrekursive iterative Lösung umwandeln läßt:

wenn sich das Problem nicht direkt lösen läßt, so ist nur noch ein einzelnes Teilproblem zu lösen,
die Lösung dieses Teilproblems gibt direkt die Lösung des Gesamtproblems.

Die hier verwendete Bezeichnung rechtsrekursiv leitet sich her aus einer Analogie mit den Formalen Sprachen: die Grammatik

Problem lösedirekt
Problem reduziere Problem

ist regulär (Klasse 3) und läßt sich in einen regulären Ausdruck umwandeln:

Problem (reduziere)* lösedirekt

Als Pseudo-Programm entspricht das der rekursiven Fassung

PROCEDURE loese(P: Problem; VAR E: Ergebnis);
BEGIN IF NOT direktloesbar(P) 
      THEN P := Teilproblem(P); loese(P, E);
      ELSE E := loesedirekt(P);
      END;
END loese;

Wichtig ist, daß hier P, die Beschreibung der Probleminstanz, Wertparameter ist, und daß der rekursive Aufruf genauso wie der Erstaufruf aussieht; dem entspricht die iterative Form:

PROCEDURE loese(P: Problem; VAR E: Ergebnis);
BEGIN WHILE NOT direktloesbar(P)
      DO P := Teilproblem(P);
      END;
      E := loesedirekt(P);
END loese;

zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36