Inhaltsverzeichnis

Rekursion

Als rekursive Methoden bezeichnet man Methoden, die sich selbst wieder aufrufen. Ein Haken dabei ist die Tatsache, dass man sich gern das Hirn dabei verrenkt, wenn die Aufrufe allzu kompliziert werden.

Schildkröte

Ich versuche ein einfaches Beispiel zu geben. Ich benutze dazu die Klasse Schildkröte, die ihr hier findet.

Für diese Methoden wird ein Applet (oder Application) mit einem Button jButton1 und einem Panel pZeichenbrett benötigt. Das Event ActionPerformed löst dann folgende Methode aus:

private void jButton1ActionPerformed(java.awt.event.ActionEvent evt) {
        Graphics stift = pZeichenbrett.getGraphics();
        Schildkröte fritz = new Schildkröte(400,300,90,stift);   
        zeichneZweiStriche (fritz, 3);
    }

Dazu fehlt natürlich noch die folgende Methode:

    private void zeichneZweiStriche (Schildkröte fritz, int nummer) {
        if (nummer>0) {
            Schildkröte fritz1 = new Schildkröte (fritz.getX(), fritz.getY(), fritz.getWinkel(), fritz.getStift());
            Schildkröte fritz2 = new Schildkröte (fritz.getX(), fritz.getY(), fritz.getWinkel(), fritz.getStift());
            fritz1.dreheLinks(15);
            fritz2.dreheRechts(15);
            fritz1.gehe(20+nummer*20);
            fritz2.gehe(20+nummer*20);
 
            zeichneZweiStriche (fritz1,nummer-1);
            zeichneZweiStriche (fritz2,nummer-1);
        }
    }

Diese Methode bietet nun interessante Variationsmöglichkeiten:

Hier wird der Methodenkopf geändert. Die Laufweite ist als zusätzlicher Parameter eingeführt und muss daher natürlich auch bei sämtlichen Aufrufen mit angegeben werden. Eine Rekursionstiefe größer als 13 macht übrigens wenig Sinn ;-) Aufgabe:

  1. Schicke Bäume finden
  2. dritten Ast hinzufügen

Fibonacci

Die Fibonacci-Zahlen sind nichts weiter als eine interessante Folge von Zahlen. Sie werden folgendermaßen definiert:

Graph

Graph

Graph

Gesucht ist eine rekursive Methode, die bei Angabe des Parameters n die n-te Fibonacci-Zahl liefert.

Eine Version, die mit Hilfe einer if-Anweisung arbeitet:

    public int fibMitIf(int n) {
        if (n==0) return 0;
        else if (n==1) return 1;
        else return fibMitIf(n-1)+fibMitIf(n-2);        
    }

Eine Version, die ohne die Hilfe einer if-Anweisung aber mit bedingten Ausdrücken arbeitet. (Also doch mit so einer Art if;-) )

    public int fibOhneIf(int n) {
        return (n==0)? 0 : ((n==1)? 1 : fibOhneIf(n-1) + fibOhneIf(n-2));
    }

Beim Ausdruck Exp1 ? Exp2 : Exp3 wird Exp2 übergeben wenn Exp1 true ist. Ansonsten hat der gesamte Asudruck den Wert Exp3. In der Zeile oben sind zwei dieser bedingten Ausdrücke verschachtelt.

OK, es gibt auch Versionen, die ohne Rekursion arbeiten…

    public int fibOhneRek(int n) {
        int z0=0, z1=1;
        if (n==0) return 0;
        for (int i=1; i<n; i++) {
            int h = z0 + z1;
            z0 = z1;
            z1 = h;
        }
        return z1;
    }

Fakultät

Die Fakultät n! einer natürlichen Zahl n, ist das Produkt sämtlicher natürlicher Zahlen von 1 bis n. (Bsp.: 5! = 5*4*3*2*1)

public int fakultaet (int n) {
    if (n==1)
        return (1);
    else
        return (n*fakultaet(n-1));
}