Rekursion mit 2 Aufrufen

[Piesenrimmel]

Hallo,

ich lerne gerade Java und bin nun beim Thema Rekursion angelangt. Bei einfachen Sachen wie Fakultät oder Collatz kann ich den Ablauf ja einigermaßen nachvollziehen, aber da gibt es eine Beispielmethode mit 2 rekursiven Aufrufen, bei der ich die Funktion gar nicht verstehe. Es geht darum, 2^n Kreuze zu schreiben:

public static void muster (int n){
if (n>0) {
muster (n-1);
IO.print ('#');
muster (n-1);
}
}

Nehmen wir an, muster wird mit n=3 aufgerufen. Nach meinem bisherigen Verständnis müsste es so ablaufen: Die if-Bedingung ist erfüllt und die Anweisungen danach werden abgearbeitet. Dann wird muster(2) aufgerufen. Dies wiederholt sich noch 2x, dann ist n=0 und die if-Bedingung ist nicht erfüllt. Dann müsste es hinter dem if-Block weitergehen, aber da kommt ja nichts mehr, also wäre die Methode zuende.
Ich kann nun nicht nachvollziehen, warum überhaupt etwas gedruckt wird, da die print-Anweisung und der 2. Rekursionsaufruf nie erreicht werden kann. Irgenwas verstehe ich da wohl falsch, aber was?

Danke vorab für jede Hilfe

 

[Androbin]

Aber natürlich kann die print-Anweisung erreicht werden:

muster( 3 ) {
    muster( 2 ) {
        muster( 1 ) {
             muster( 0 ) { }
             IO.print( '#' );
             muster( 0 ) { }
        }
        IO.print( '#' );
        muster( 1 ) {
             muster( 0 ) { }
             IO.print( '#' );
             muster( 0 ) { }
        }
    }
    IO.print( '#' );
    muster( 2 ) {
        muster( 1 ) {
             muster( 0 ) { }
             IO.print( '#' );
             muster( 0 ) { }
        }
        IO.print( '#' );
        muster( 1 ) {
             muster( 0 ) { }
             IO.print( '#' );
             muster( 0 ) { }
        }
    }
}

 

[njans]

Wenn n <= 0 wird, dann endet deine Rekursion, indem diese nichts mehr macht.
Das heißt du gehst erst immer wieder in denn ersten Rekursionszweig bis n <= 0 wird. Dann gehst du einen Schritt zurück und gibst dein # aus. Danach gehst du in die 2te Rekursion und diese wird dann abgearbeitet. dann gehst du eine Rekursionstiefe zurück und wiederholst das.

 

[stg]

Schon bei den einfachen Fällen n=0, oder meinetwegen auch n=1 kann man sofort erkennen, dass die Funktion nicht das gewünschte leistet.

 

[arilou]

Schon bei den einfachen Fällen n=0, oder meinetwegen auch n=1 kann man sofort erkennen, dass die Funktion nicht das gewünschte leistet.

Sie ist aber dicht dran, sie schreibt 2^n-1 Kreuze: durch die zwei Rekursionsäste findet für jedes n eine Verdopplung statt, dadurch ist der "Exponentiell zur Basis 2"-Faktor schon mal gegeben.