Rekursiven Stack

[Snaer]

Guten Tag,

Ich möchte gerne die Ausgabe von folgenden Code nachvollziehen:

public class Recursive {
    
    public static void main(String[] args) {
        calc(3);
    }
    
    public static void calc(int n) {
        if(n <= 0) return;
        calc(n-1);
        System.out.print(n);
        calc(n-2);
        System.out.print(n);
    }   
}

Bei einem anderen Beispiel mit nur einem rekursiven Aufruf und nur einem print Aufruf empfand ich es als ziemlich leicht zu durchschauen weswegen die Ausgabe aussieht wie sie es tat. Jedoch verwirrt mich die Ausgabe bei diesem Code. Mit dem Wert 3 erhält man damit 11223113.
Mich verwirrt dabei wie genau der Code nun vorgeht, die Methode ruft sich ja immer wieder selbst auf bis n = 0 ist, bei dem Beispiel mit 3.
Wird dabei nun der erste rekursive Ausdruck solange durch geführt bis die 3 auf 0 ist und danach der 2.? Oder werden die beiden nacheinander ausgeführt und beginnt die Methode dann wieder von vorne?

 

[LimDul]

Gehen wir das doch mal Zeilenweise durch.

Aufruf von calc mit n = 3
Tiefe 1, Zeile 1: Bedingung falsch, wird weiter ausgeführt
Tiefe 1, Zeile 2: Aufruf von calc mit n = 2 => Ab in Tiefe 2
Tiefe 2, Zeile 1: Bedingung falsch, wird weiter ausgeführt
Tiefe 2, Zeile 2: Aufruf von calc mit n = 1 => Ab in Tiefe 3
Tiefe 3, Zeile 1: Bedingung falsch, wird weiter ausgeführt
Tiefe 3, Zeile 2: Aufruf von calc mit n = 0 => Ab in Tiefe 4
Tiefe 4, Zeile 1: Bedingung war, Rücksprung in Tiefe 3
Tiefe 3, Zeile 3: Ausgabe von n ( ist hier 1)
Tiefe 3, Zeile 4_ Aufruf von clac mit n = -1 => Ab in Tiefe 4
Tiefe 4, Zeile 1: Bedingung war, Rücksprung in Tiefe 3
Tiefe 3, Zeile 5: Ausgabe von n ( ist hier 1), Methode zuende, Rücksprung in Tiefe 2
Tiefe 2, Zeile 3: Ausgabe von n (ist hier 2)
Tiefe 2, Zeile 4: Aufruf von calc mit n=0 => Ab in Tiefe 3
Tiefe 3, Zeile 1: Bedingung war, Rücksprung in Tiefe 2
Tiefe 2, Zeile 5: Ausgabe von (ist hier 2)), Methode zuende, Rücksprung in Tiefe 1
Tiefe 1, Zeile 3: Ausgabe von n (ist hier 3)
Tiefe 1, Zeile 4: Aufruf von calc mit n=1 => Ab in Tiefe 2
Tiefe 2, Zeile 1: Bedingung falsch, wird weiter ausgeführt
usw.

 

[Snaer]

Also wenn ich es richtig verstanden habe durchläuft der Code zunächst den ersten rekursiven Aufruf und dann anschließend mit den einzelnen Ergebnissen der ersten Zeile dann den 2. Aufruf bis alle möglichen Werte > 0 durch sind ?

 

[Blender3D]

Ich möchte gerne die Ausgabe von folgenden Code nachvollziehen:

Der folgende Code verdeutlicht die Aufrufreihenfolge. "F" steht für den 1ten Funktionsaufruf und "S" für den 2ten.

public class Recursive {
    public static int cntFirst = 0;
    public static int cntSecond = 0;
    public static String out = "";

    public static void main(String[] args) {
        calc(3);
        System.out.println("\n" + out);
    }

    public static void calc(int n) {
        if (n <= 0)
            return;
        System.out.println("1. calc()\t" + cntFirst);
        System.out.println("2. calc()\t" + cntSecond);
        System.out.println("number\t" + n);
        System.out.println("------------------");
        cntFirst++;
        calc(n - 1);
        out += " F"+n;
        cntSecond++;
        calc(n - 2);
        out += " S"+n;
    }
}

Ergbnis: F1 S1 F2 S2 F3 F1 S1 S3

 

[Plauzi92]

Wenn ich das richtig verstanden habe müsste der Aufrufstack der Funktion also folgerndermaßen aussehen:

s = []
s = [calc(3)]
s = [calc(3), calc(2)]
s = [calc(3), calc(2), calc(1)]
s = [calc(3), calc(2), calc(1), calc(0)]
s = [calc(3), calc(2), calc(1),]
s = [calc(3), calc(2), calc(1), calc(-1)]
s = [calc(3), calc(2), calc(1)]
s = [calc(3), calc(2)]
s = [calc(3), calc(2), calc(0)]
s = [calc(3), calc(2)]
s = [calc(3)]
s = [calc(3), calc(1)]
s = [calc(3), calc(1), calc(-1)]
s = [calc(3), calc(1)]
s = [calc(3)]
s = []

 

[lennero]

Wenn ich das richtig verstanden habe müsste der Aufrufstack der Funktion also folgerndermaßen aussehen:

3
2 1
1 0 0 -1
0 -1

 

[Meniskusschaden]

Wenn ich das richtig verstanden habe müsste der Aufrufstack der Funktion also folgerndermaßen aussehen:

Meines Erachtens fehlt da ein Aufruf von calc(0). Habe ich hier mal eingefügt:

s = []
s = [calc(3)]
s = [calc(3), calc(2)]
s = [calc(3), calc(2), calc(1)]
s = [calc(3), calc(2), calc(1), calc(0)]
s = [calc(3), calc(2), calc(1),]
s = [calc(3), calc(2), calc(1), calc(-1)]
s = [calc(3), calc(2), calc(1)]
s = [calc(3), calc(2)]
s = [calc(3), calc(2), calc(0)]
s = [calc(3), calc(2)]
s = [calc(3)]
s = [calc(3), calc(1)]
s = [calc(3), calc(1), calc(0)] // Dieser Aufruf fehlt
s = [calc(3), calc(1)]          // und deshalb fehlt auch diese Zeile
s = [calc(3), calc(1), calc(-1)]
s = [calc(3), calc(1)]
s = [calc(3)]
s = []

Hier ist noch mal eine andere Darstellung: