Kurs:Programmieren in Oberon/Kapitel 6

Dieses Kapitel gehoert zum Kurs Programmieren in Oberon des Fachbereichs Informatik.

Immer das gleiche - Rekursionen

Also schön, die Grundlagen des Programmierens sitzen schon fest, die Selbstsicherheit pulsiert in den Adern, und dann kommt so ein Ding - Rekursionen. Obwohl wir (hoffentlich) alle diese Dinger in der Mathematik schon mal gesehen haben, fällt es immer noch schwer, sie zu verstehen.

Wir wollen also eine berühmte Rekursion, das Euklidsche Verfahren zur Bestimmung eines ggTs (fuer die, die in der Mathemaitik gepennt haben, das ist der groesste gemeinsame Teiler), durch eine rekursive Prozedur ausdrucken. Es soll ein Modul namens MeinModul mit einer Prozedur namens ggT, welche die Zahlen n und m einliest und den grössten gemeinsamen Teiler zurückgibt erzeugt werden.

Aus dem Leben gegriffen

Wie gesagt, haben wir alle diese Dinger schon mal gesehen, und zwar in der Mathematik. Dort ist die Fibonacci-Reihe z.B. so beschrieben:

${\mbox{Fib}}(0)$	$\rightarrow$	$1$
${\mbox{Fib}}(1)$	$\rightarrow$	$1$
${\mbox{Fib}}(n)$	$\rightarrow$	${\mbox{Fib}}(n-1)+{\mbox{Fib}}(n-2)$

Wenn wir also selber eine Fibonacci-Prozedur schreiben, welche n als Parameter erhält und eine Zahl zurückgibt, muss diese Prozedur, falls n > 1, sich selber aufrufen. Dies ist kein Problem.

PROCEDURE Fib ( n : INTEGER ) : INTEGER;
    BEGIN
        IF n < 2 THEN
            RETURN 1;
        ELSE
            RETURN Fib(n-1) + Fib(n-2);
        END;
    END Fib;

Das ganze sieht erstaunlich einfach aus und ist es sogar auch. Eine erste Bedingung muss dafür sorgen, dass die Prozedur sich nicht endlos selber aufruft, ist diese nicht erfüllt, so ruft die Prozedur sich selber auf.

Beim Entwurf der Prozedur ist immer darauf zu achten, dass die Abbruchbedingung (in unserem Fall n < 2) irgendwann erfüllt wird. Bei uns muss n immer kleiner als ein gewisser Wert sein. Die Prozedur ruft sich immer entweder mit n-1 oder n-2 selbst auf, also wird n immer kleiner, die Rekursion hört irgendwann auf.

Same shit, new Variables

Das Beispiel der Fibonacci-Reihe ist ziemlich einfach, da die Prozedur keine Variablen enthält, und sich darum nie die Frage stellt, was mit lokalen Variablen passiert. Nehmen wir ein etwas komplizierteres Beispiel, nämlich ein Fahrzeug, welches ein Feld (m * n) von links oben nach rechts unten traversieren muss. Das Terrain auf dem Feld ist nicht immer gleich, sondern variiert von 1 bis 10 (1 schnell, 10 langsam). Er muss den schnellsten Weg finden und melden, wie lange dieser war.

Wir müssen nun eine Prozedur schreiben, die für ein Fahrzeug an der Position x,y entscheidet, ob er besser nach rechts oder nach unten geht, und diesen Weg, plus den Wert des Feldes an der Position x,y zurückgibt. Grob ausgelegt gibt es so was

PROCEDURE Fahr ( x, y : INTEGER ) : INTEGER;
    VAR
        rechts, runter : INTEGER;
    BEGIN
        IF x,y nicht im feld (also nicht in n oder m) THEN
            RETURN MAX(INTEGER);
        END; (* dieser weg soll nicht gewaehlt werden *)
        IF position ist unten rechts THEN
            RETURN feld[x,y];
        END (* man ist am Ende gelangt *)
        rechts := Fahr(x+1, y);
        runter := Fahr(x,y+1);
        IF rechts > runter THEN
            RETURN feld[x,y] + runter;
        ELSE
            RETURN feld[x,y] + rechts;
        END; (* nimm den besseren Weg *)
    END Fahr;

Was passiert nun mit den Werten von rechts und runter wenn die Prozedur sich selber aufruft? Werden sie von der zweiten Instanz von Fahr überschrieben?

Nee! Man kann es so sehen, dass wenn eine rekursive Prozedur sich selber aufruft, wird so getan, als ob sie eine andere Prozedur, halt mit dem gleichen Namen aber separate Variablen, aufrufen würde. Die Variablen in jeder Instanz von Fahr sind ihr eigen und werden bei den verschachtelten Prozeduraufrufen jedesmal neu angelegt, die Werte der aufrufenden Instanz bleiben erhalten.

Bauen wir also nun unsere Prozedur Fahr so aus, dass sie Funktioniert. Da wir schon daran sind, bauen wir auch ein Modul rund herum.

MODULE Fahrzeug;

    IMPORT
        In, Out;

    VAR
        feld : ARRAY 20,20 OF INTEGER;
        m, n : INTEGER;

    PROCEDURE Einlesen;
        VAR
            i, j : INTEGER;
        BEGIN
            In.Open;
            In.Int(m); In.Int(n);
            FOR i := 0 TO m-1 DO
                FOR j := 0 TO n-1 DO
                    In.Int(feld[i,j]);
                END;
            END;
        END Einlesen;

    PROCEDURE Fahr ( x, y : INTEGER ) : INTEGER;
        VAR
            rechts, runter : INTEGER;
        BEGIN
            IF (x >= m) OR (x < 0) OR (y >= n) OR (y < 0) THEN
                RETURN MAX(INTEGER);
            END;
            IF (x = m-1) & (y = n-1) THEN
                RETURN feld[x,y];
            END;
            rechts := Fahr(x+1,y);
            runter := Fahr(x,y+1);
            IF rechts > runter THEN
                RETURN runter + feld[x,y];
            ELSE
                RETURN rechts + feld[x,y];
            END;
        END Fahr;

    PROCEDURE Los*;
        BEGIN
            Einlesen;
            Out.String("Der kuerzeste Weg hat die Laenge: ");
            Out.Int(Fahr(0,0),2); Out.Ln;
        END Los;

    BEGIN
        Out.Open;
    END Fahrzeug.

So, wenn wir jetzt die Prozedur Fahr uns anschauen, haben wir zwei Abbruchbedingungen: wenn das Fahrzeug am Ziel ist und wenn es aus dem Feld raus ist. Wir berechnen den Weg nach unten und den nach rechts und nehmen den besseren, addieren unser gegenwärtiges Feld dazu und springen zurück.

Euklid meets Oberon

Also gut, wenn ihr das Beispiel mit dem Fahrzeug nicht hundertprozentig verstanden habt, ist es nicht so schlimm: Hauptsache ist, dass ihr die wesentlich einfachere Euklidische Rekursion versteht. In der Mathematik sind folgende Regeln bestimmt:

${\mbox{ggT}}(x,x)$	$\rightarrow$	$x$
${\mbox{ggT}}(x,0)$	$\rightarrow$	$0$
${\mbox{ggT}}(x,y)$	$\rightarrow$	${\mbox{ggT}}(y,x)$
${\mbox{ggT}}(x,y)$	$\rightarrow$	${\mbox{ggT}}(x{\mbox{ mod }}y,y)$

Wir haben also zwei Abbruchbedingungen und zwei mögliche Berechnungen. Wenn man sich diese Berechnungen anschaut, kann man sie beide in einem Schritt erledigen: ist y grösser als x, so ist x MOD y gleich x, es ändert sich aber nichts. Ist hingegen y kleiner als x, so wird x MOD y kleiner sein als y. Damit wir garantieren, das der ggT nie gleich ist, und die Rekursion somit nie in eine endlos-Schleife gerät, können wir gleichzeitig MOD-rechnen und umkehren, und zwar so:

${\mbox{ggT}}(x,y)\rightarrow {\mbox{ggT}}(y,x{\mbox{ mod }}y)$

Wenn wir jetzt das ganze so verpacken, dass es Oberon versteht, kriegen wir sowas:

MODULE MeinModul;

    IMPORT
        In, Out;

    PROCEDURE Euklid ( x, y : INTEGER ) : INTEGER;
        BEGIN
            IF (y = 0) OR (x = y) THEN
                RETURN x;
            ELSE
                RETURN Euklid(y,x MOD y);
            END;
        END Euklid;

    PROCEDURE ggT*;
        VAR
            x, y : INTEGER;
        BEGIN
            In.Open; In.Int(x); In.Int(y);
            Out.String("der ggT von "); Out.Int(x,2);
            Out.String(" und "); Out.Int(y,2);
            Out.String(" ist: "); Out.Int(Euklid(x,y),2);
            Out.Ln;
        END ggT;

    BEGIN
        Out.Open;
    END MeinModul.