Methoden Rekursion nachvollziehen

[MWin123]

Hallo, ich bin Java Anfänger und versuche die rekursive Programmierung zu erlernen.

Mir ist leider nicht ganz klar, wie Rekursion mit verschiedenen Variablen funktioniert.

Folgendes Beispiel:

public class Aufgabe3 {

    private static int simple(int line) {
        System.out.println("" /* TODO: Ausdruck anpassen */);
        return (-1 /* TODO: Ausdruck anpassen */);
    }


    private static int rec(int i, int line) {
        System.out.println("" /* TODO: Ausdruck anpassen */);
        if (i > 0) {
            int a /* TODO: Variable anpassen */ = rec(i - 1, (-1 /* TODO: Ausdruck anpassen */));
            int b /* TODO: Variable anpassen */ = simple(-1 /* TODO: Ausdruck anpassen */);
            int c /* TODO: Variable anpassen */ = rec(i - 1, (-1 /* TODO: Ausdruck anpassen */));
            return (-1 /* TODO: Ausdruck anpassen */);
        }
        return (-1 /* TODO: Ausdruck anpassen */);
    }
}

Anhand der Aufgabe sollen die Methodenaufrufe nachvollzogen und ein Protokoll ausgegeben werden.
Daher sollte für rec(4,0) folgendes ausgeben werden:

1 rec(4, 0)
2 rec(3, 1)
3 rec(2, 2)
4 rec(1, 3)
5 rec(0, 4)
6 simple(5)
7 rec(0, 6)
8 simple(7)
9 rec(1, 8)
10 rec(0, 9)

Nur wie gehe ich hier jetzt vor?

Einfache rekursive Methoden beherrsche ich, nur wie funktioniert das ganze mit Variablen, die als rekursive Methode definiert sind? Ich kann ja nur einen Int Wert zurückgeben.
Wenn ich mit int a die ersten 5 Zeilen ausgeben will und nur einen Wert zurückgeben kann, würde ich die fortlaufende Nummer nehmen. Nur wie komme ich jetzt in die Methode simple rein?

Komplizierter wird es noch dadurch, dass ich nur die mit TODO gekennzeichneten Bereiche anpassen darf.

 

[Flown]

Was redest du da mit Variablen und Funktionen. a, b, c sind ganz einfache ints.

Sieh dir das Protokoll doch näher an.

Jetzt musst du nur die Aufrufparameter und die Rückgabeparameter so hintrimmen, dass sie dem Protokoll entsprechen.

Fürs erste kann ich dir sagen, dass du mal die System.out.println machst und dir genau mal die i und lines ausgibst, genau so wie in dem Protokoll. Dann spielst du mit den Werten herum und et voilà.

 

[MWin123]

Ich wollte es nur allgemein halten und habe daher Variablen statt int gesagt.
Wären es floats oder Strings würde ich mich genau so wenig auskennen.

Mit viel rumprobieren stimmen nun die ersten 7 Zeilen:

1 rec(4, 0)
2 rec(3, 1)
3 rec(2, 2)
4 rec(1, 3)
5 rec(0, 4)
6 simple(5)
7 rec(0, 6)
5 simple(4)
6 rec(1, 5)
7 rec(0, 6)
8 simple(7)
9 rec(0, 8)
4 simple(3)
5 rec(2, 4)
6 rec(1, 5)
7 rec(0, 6)
8 simple(7)
9 rec(0, 8)
7 simple(6)
8 rec(1, 7)
9 rec(0, 8)
10 simple(9)
11 rec(0, 10)
3 simple(2)
4 rec(3, 3)
5 rec(2, 4)
6 rec(1, 5)
7 rec(0, 6)
8 simple(7)
9 rec(0, 8)
7 simple(6)
8 rec(1, 7)
9 rec(0, 8)
10 simple(9)
11 rec(0, 10)
6 simple(5)
7 rec(2, 6)
8 rec(1, 7)
9 rec(0, 8)
10 simple(9)
11 rec(0, 10)
9 simple(8)
10 rec(1, 9)
11 rec(0, 10)
12 simple(11)
13 rec(0, 12)

Der Code schaut zur Zeit so aus:

/*    Aufgabe3) Rekursion nachvollziehen


    Die Methoden 'simple' und 'rec' sind nach folgendem Muster aufgebaut:


    private static int simple(int line) {
        System.out.println(...);
        return ...;
    }


    private static int rec(int i, int line) {
         System.out.println(...);
         if (i > 0) {
            ... = rec(i - 1, ...);
            ... = simple(...);
            ... = rec(i - 1, ...);
            return ...;
        }
        return ...;
    }


    Ersetzen Sie alle '...' in diesem Muster durch Ausdrücke, sodass ein Aufruf von rec(4, 0) ein Protokoll aller
    Methodenaufrufe erstellt. Jeder Eintrag im Protokoll gibt eine fortlaufende Nummer des Aufrufs, den Namen der
    aufgerufenen Methode und die Werte aller Parameter an. Die Parameter 'line' in 'simple' und 'rec' sowie die
    zurückgegebenen Ergebnisse stehen dabei jeweils für die fortlaufende Nummer der zuletzt ausgegebenen Zeile im
    Protokoll. Die ersten zehn Zeilen des Protokolls sollen folgendermaßen aussehen:


    1 rec(4, 0)
    2 rec(3, 1)
    3 rec(2, 2)
    4 rec(1, 3)
    5 rec(0, 4)
    6 simple(5)
    7 rec(0, 6)
    8 simple(7)
    9 rec(1, 8)
    10 rec(0, 9)




    Zusatzfragen:
    1. Wodurch kommt die große Anzahl der Zeilen im Protokoll zustande?
    2. Wie stark wirkt sich eine Änderung des ersten Arguments von 'rec' auf die Anzahl der Zeilen im Protokoll aus?
       Wie viele Zeilen würde man z.B. mit 2, 6, 10 oder 15 statt 4 bekommen?
    5. Wie viele Aufrufe von 'rec' sind maximal zur selben Zeit aktiv?
    4. Durch welche einzelne Anweisung könnte man die vier Anweisungen in der bedingten Anweisung in 'rec' ersetzen,
       ohne die Semantik des Programms zu ändern?
*/
public class Aufgabe3 {


    private static int simple(int line) {
        System.out.println(line + 1 + " simple(" + line + ")" /* TODO: Ausdruck anpassen */);
        return (line + 1 /* TODO: Ausdruck anpassen */);
    }


    private static int rec(int i, int line) {
        System.out.println(line + 1 + " rec(" + i + ", " + line + ")"/* TODO: Ausdruck anpassen */);
        if (i > 0) {
            int a /* TODO: Variable anpassen */ = rec(i - 1, (line + 1 /* TODO: Ausdruck anpassen */));
            int b /* TODO: Variable anpassen */ = simple(line + 2 /* TODO: Ausdruck anpassen */);
            int c /* TODO: Variable anpassen */ = rec(i - 1, (b /* TODO: Ausdruck anpassen */));
            return (-1 /* TODO: Ausdruck anpassen */);
        }
        return (-1 /* TODO: Ausdruck anpassen */);
    }


    // just for testing ...
    public static void main(String[] args) {
        // Die Implementierung von main kann ohne Auswirkung auf die Korrektheit der Lösung geändert werden.
        rec(4, 0);
    }
}

Was mir noch unklar ist:

1. Warum wird simple wiederholt ausgeführt? rec() wird ja solange wiederholt, bis i=0

2. Ich habe hier simple das Argument (line + 2) gegeben. Damit bekommt zumindest der erste Aufruf von simple den richtigen Wert. Wieso ist mir aber nicht klar.

int b /* TODO: Variable anpassen */ = simple(line + 2 /* TODO: Ausdruck anpassen */);

3. Was soll ich denn bei rec() und simple() zurückgeben lassen?
4. Was mache ich mit int c?

 

[Flown]

Schau dir bitte nochmal Rekursionen an. Nimm Stift + Papier in die Hand und zeichne deinen Algorithmus mit der Hand auf (Z.b. für i = 2 & line = 0 => da sollten 10 Zeilen rauskommen bei den - bei rec(4, 0) sind es übrigens 45). Beziehungsweise starte den Debugger und schau dir mal an, was du da aufrufst und wie oft!

Ich kann dir jetzt nicht mehr sagen, ohne dir gleich die Lösung zu verraten.

 

[MWin123]

So, heute das erste Mal den Debugger benutzt. Damit lassen sich die Aufrufe doch ein Stück leichter nachvollziehen.

Wirklich verstanden habe ich es jedoch noch nicht, aber immerhin passt jetzt die Ausgabe!

1 rec(4, 0)
2 rec(3, 1)
3 rec(2, 2)
4 rec(1, 3)
5 rec(0, 4)
6 simple(5)
7 rec(0, 6)
8 simple(7)
9 rec(1, 8)
10 rec(0, 9)
11 simple(10)
12 rec(0, 11)
13 simple(12)
14 rec(2, 13)
15 rec(1, 14)
16 rec(0, 15)
17 simple(16)
18 rec(0, 17)
19 simple(18)
20 rec(1, 19)
21 rec(0, 20)
22 simple(21)
23 rec(0, 22)
24 simple(23)
25 rec(3, 24)
26 rec(2, 25)
27 rec(1, 26)
28 rec(0, 27)
29 simple(28)
30 rec(0, 29)
31 simple(30)
32 rec(1, 31)
33 rec(0, 32)
34 simple(33)
35 rec(0, 34)
36 simple(35)
37 rec(2, 36)
38 rec(1, 37)
39 rec(0, 38)
40 simple(39)
41 rec(0, 40)
42 simple(41)
43 rec(1, 42)
44 rec(0, 43)
45 simple(44)
46 rec(0, 45)

/*    Aufgabe3) Rekursion nachvollziehen

    Die Methoden 'simple' und 'rec' sind nach folgendem Muster aufgebaut:


    private static int simple(int line) {
        System.out.println(...);
        return ...;
    }


    private static int rec(int i, int line) {
         System.out.println(...);
         if (i > 0) {
            ... = rec(i - 1, ...);
            ... = simple(...);
            ... = rec(i - 1, ...);
            return ...;
        }
        return ...;
    }


    Ersetzen Sie alle '...' in diesem Muster durch Ausdrücke, sodass ein Aufruf von rec(4, 0) ein Protokoll aller
    Methodenaufrufe erstellt. Jeder Eintrag im Protokoll gibt eine fortlaufende Nummer des Aufrufs, den Namen der
    aufgerufenen Methode und die Werte aller Parameter an. Die Parameter 'line' in 'simple' und 'rec' sowie die
    zurückgegebenen Ergebnisse stehen dabei jeweils für die fortlaufende Nummer der zuletzt ausgegebenen Zeile im
    Protokoll. Die ersten zehn Zeilen des Protokolls sollen folgendermaßen aussehen:


    1 rec(4, 0)
    2 rec(3, 1)
    3 rec(2, 2)
    4 rec(1, 3)
    5 rec(0, 4)
    6 simple(5)
    7 rec(0, 6)
    8 simple(7)
    9 rec(1, 8)
    10 rec(0, 9)




    Zusatzfragen:
    1. Wodurch kommt die große Anzahl der Zeilen im Protokoll zustande?
    2. Wie stark wirkt sich eine Änderung des ersten Arguments von 'rec' auf die Anzahl der Zeilen im Protokoll aus?
       Wie viele Zeilen würde man z.B. mit 2, 6, 10 oder 15 statt 4 bekommen?
    5. Wie viele Aufrufe von 'rec' sind maximal zur selben Zeit aktiv?
    4. Durch welche einzelne Anweisung könnte man die vier Anweisungen in der bedingten Anweisung in 'rec' ersetzen,
       ohne die Semantik des Programms zu ändern?
*/
public class Aufgabe3 {


    private static int simple(int line) {
        System.out.println(line + 1 + " simple(" + line + ")" /* TODO: Ausdruck anpassen */);
        return (line + 1/* TODO: Ausdruck anpassen */);
    }


    private static int rec(int i, int line) {
        System.out.println(line + 1 + " rec(" + i + ", " + line + ")"/* TODO: Ausdruck anpassen */);
        if (i > 0) {
            int a /* TODO: Variable anpassen */ = rec(i - 1, (line +1 /* TODO: Ausdruck anpassen */));
            int b /* TODO: Variable anpassen */ = simple(a /* TODO: Ausdruck anpassen */);
            int c /* TODO: Variable anpassen */ = rec(i - 1, (b /* TODO: Ausdruck anpassen */));
            return (c /* TODO: Ausdruck anpassen */);
        }
        return (line + 1 /* TODO: Ausdruck anpassen */);
    }


    // just for testing ...
    public static void main(String[] args) {
        // Die Implementierung von main kann ohne Auswirkung auf die Korrektheit der Lösung geändert werden.
        rec(4, 0);
    }
}