Rekursion

[java.schüler]

Hallo!
Ich möchte den Binomialkoeffizienten zweier Zahlen n und k rekursiv berechen.
Das funtkioniert mit folgendem Code:

//BinomialKoeffizient n over k  recursiv
    static long binCoeff(long n, long k) {
        if(k == 0) return 1;
        else if(k>n) return 0;
        else return binCoeff(n-1, k-1) + binCoeff(n-1, k);

Wenn jetzt dann aber binCoeff(n-1, k-1) ruft diese dann ja wiederum binCoeff(n-1,k-1) + binCoeff(n-1,k) auf, wodurch sich das ganze ebenfalls wiederholt.
Gleichzeitig würde ja auch der zweite Teil binCoeff(n-1,k) das selbe tun.

Mir ist klar, dass das solange geht bis k == 0 bzw k>n erreicht wird.
Das wäre dann bei n=3, k=0 das erste mal der Fall.(das aber nur beim ersten Ausdruck binCoeff(n-1,k-1))
Was genau passiert mit dem Wert 1 dann, der zurückgegeben wird? Womit wird dieser dann addiert? Bzw. wie funktioniert die Rekursion weiter?

Vielen Dank für eure Antworten gleich im Voraus!

 

[java.schüler]

Wenn man von den Werten n = 5, k = 2 ausgeht!

 

[Joose]

Schreib dir doch auf mit Stift + Papier auf was der Reihe nach alles aufgerufen wird

Beispiel

binCoeff(5, 2)
   binCoeff(4, 1)
       binCoeff(3, 0)
           return 1;
       binCoeff(3, 1)
           binCoeff(2, 0)
               return 1;
           binCoeff(2, 1)
               binCoeff(1, 0)
                   return 1;
               binCoeff(1, 1)
                   binCoeff(0, 0)
                       return 1;
                   binCoeff(0, 1)
                       return 0;
   binCoeff(4, 2)
       binCoeff(3, 1)
           binCoeff(2, 0)
               return 1;
           binCoeff(2, 1)
               binCoeff(1, 0)
                   return 1;
               binCoeff(1, 1)
                   binCoeff(0, 0)
                       return 1;
                   binCoeff(0, 1)
                       return 0;
       binCoeff(3, 2)
           binCoeff(2, 1)
               binCoeff(1, 0)
                   return 1;
               binCoeff(1, 1)
                   binCoeff(0, 0)
                       return 1;
                   binCoeff(0, 1)
                       return 0;
           binCoeff(2, 2)
               binCoeff(1, 1)
                   binCoeff(0, 0)
                       return 1;
                   binCoeff(0, 1)
                       return 0;
               binCoeff(1, 2)
                   return 0;

Wenn du dir unsicher bist was der Reihe nach aufgerufen wird, dann gib am Anfang der Methode eine Konsolenausgabe rein mit Methodenname + Parameterwerten, dann sollte das klarer werden.

 

[java.schüler]

Viele Danke, jetzt ist alles klar!
Habs mir als Baum aufgezeichnet.

Wie genau muss dann diese Konsolenausgabe ausschaue?
Also, damit ich alle Schritte einzeln bekomme, so wie oben?
Habs mit System.out.println(binCoeff(5,2));
versucht. Da bekommt man eben nur das Ergebnis.

 

[Joose]

Du musst dir den entsprechenden String selber zusammenbauen

System.out.println("binCoeff(" + n + ", " + k + ")");

 

[java.schüler]

Danke dir!