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!🙂