# Binomialkoeffizient rekursiv berechnen



## khstgt (7. Jan 2010)

bin gerade dabei zu versuchen ein programm  zu schreiben, welches den binomialkoeffizient für zwei übergebene zahlen berechnet.


Fehlermeldung:
Exception in thread "main" java.lang.RuntimeException: Uncompilable source code - cannot find symbol
  symbol:   variable calculateBinomialCoefficient
  location: class grundlagenuebungen.BinomialCoefficient

kann mirjemand sagen woran es liegt?

vielen Dank


----------



## mmeyer1987 (7. Jan 2010)

Du hast die Klammern vergessen und die Parameter nicht übergeben. Probiers mal so: 


```
package grundlagenuebungen;
 
import javax.swing.JOptionPane;
 
public class BinomialCoefficient {
 
    public static void main (String [] args){
 
  int n = Integer.parseInt (JOptionPane.showInputDialog ("Bitte geben Sie n ein: "));
  int k = Integer.parseInt (JOptionPane.showInputDialog ("Bitte geben sie k ein: "));
 
  JOptionPane.showMessageDialog (null, "Binomialkoeffizient " + calculateBinomialCoefficient(n,k));
 
    }
  public static int calculateBinomialCoefficient (int n, int k)
   {
      if (k == 1)
         return n;
      else if (n >= k && k == 0)
         return 1;
      else
         return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
 
   }
}
```

Wobei ich glaube, das das inhaltlich nicht stimmt. Wikipedia gibt folgenden Pseudocode:



			
				Wikipedia hat gesagt.:
			
		

> binomialkoeffizient(n, k)
> 1  wenn k = 0 dann rückgabe 1
> 2  wenn 2k > n
> 3      dann führe aus ergebnis \leftarrow binomialkoeffizient(n, n-k)
> ...


 Quelle: Wikipedia

Gruß!


----------



## bademaister (15. Jan 2010)

Hallo,
ich hab einmal eine Frage und zwar:

```
(n * calculateBinomialCoefficient(n - 1, k - 1) / k)
```
Was macht diese Zeile genau? Ich versteh das irgendwie nicht.
Ich hoffe da kann mir jmd helfen ???:L


----------



## SlaterB (15. Jan 2010)

ein Methodenaufruf mit irgendwelchen Parametern und der Rückgabewert int  wird noch weitergerechnet,
was kann man denn daran prinzipiell nicht verstehen?

warum man das so macht und der Gesamtablauf von zig Aufrufen zum richtigen Ergebnis führt,
ist dagegen schon etwas schwieriger, dazu muss man Rekursion kennen und eine Vorstellung für den Gesamtalgorithmus haben


----------



## bademaister (15. Jan 2010)

Ja, das ist mir shcon klar. Nur wie kann der mit dieser Zeile 6 aus 49 ausrechnen?
/e
Also wie man prinzipiell den Binomialkoeffezienten ausrechnet ist mir schon klar.
Ich würde dies allerdings mit Fakultäten machen.
Andere Programme die ich hier im forum gesehen habe sind mit einer for schleife geschrieben wurden und sind deutlich länger.
Kannst du mir vllt den ersten schritt nennen wie der das hier ausrechnet?


----------



## eRaaaa (15. Jan 2010)

Mit der Zeile alleine nicht. Das ist ja ein rekursiver Aufruf, d.h. die methode würde (in deinem Beispiel) sich 5 mal selber aufrufen, bzw Allgemein gesagt, bis irgendwann einer der beiden vorherigen if-Abfragen zutreffen, weil dann wird ja nicht noch mal rekursiv, sondenr direkt n oder 1 zurückgegeben.

In dem Pseudocode von oben (der von Wiki) könnte man 6 aus 49 auch ohne Rekursion berechnen, was Performance-mäßig daher irgendwie schöner ist


----------



## bademaister (15. Jan 2010)

Rechnet er dann also folgendermaßen?
49*BC(48,5)/6.....->springe wieder hoch. 
Im nächsten Schritt dann:
48*BC(47,4)/5....
47*BC(46,3)/4....
46*BC(45,2)/3....
45*BC(44,1)/2....
44*BC(43,2)/1....
und speichert die ergebnisse sodass zum schluss: (49/6)*(48/5)*(47/4)*(46/3)*(45/2)*(44/1) stehen bleibt?


----------



## SlaterB (15. Jan 2010)

was genau gerechnet wird, kannst du doch durch ein System.out.println() auf jeden einzelnen Schritt genau herausfinden,
evtl. temporär zusätzliche Variablen/ Parameter einfügen wie Runde/ Rekursionstiefe,


----------



## eRaaaa (15. Jan 2010)

bademaister hat gesagt.:


> Rechnet er dann also folgendermaßen?
> 49*BC(48,5)/6.....->springe wieder hoch.
> Im nächsten Schritt dann:
> 48*BC(47,4)/5....
> ...



Nein nicht ganz. Bei k==1 ist ja Schluß! Da wird ja dann in dem Beispiel direkt n also 44 zurückgegeben, so dass du dann folgenden Term eig. stehen hast:

49*(48*(47*(46*(45*44/2)/3)/4)/5)/6


----------

