Binomialkoeffizient ausrechnen, Exception in thread "main" java.lang.StackOverflowError

[javaerd]

Hallo,

ich möchte den Binomialkoeffizient mittels Rekursion ausrechnen. Als Datentypen habe ich extra long ausgewählt, denoch bekomme ich einen Fehler.
Ist dieser Fehler, aufgrund des überlaufes oder wo genau liegt das Problem?

        .....

        binomialkoeffizient();
    }
   
    public static void binomialkoeffizient(){
       
        long result = 0;
        int n = 49;
        int k = 6;
       
        result = (n * faculty(n-1)) / ((faculty(k) * faculty(n-k)));
        System.out.println(result);
    }
   
    public static long faculty(int number){
        return number * faculty(number-1);     //<<<<<Hier ist der Fehler , laut Eclipse
    }

 

[Thallius]

Da Du überhaupt keine Abbruchbedingung in deiner Rekursiven Methode hast muss der Stack irgendwann überlaufen...

 

[javaerd]

Stimmt, aber wenn ich jetzt eine Abbruchbedingung hinzufüge, dann liefert mir die Methode ein fasches Ergebnis. Also am Ende ist ya number = 1, dann wird einfach nur 1 zurückgegeben.

    public static long faculty(int number){
        if(number == 0) return number;
        if(number == 1) return number;
        return number * faculty(number-1);
    }

 

[Thallius]

und warum soll das nicht funktionieren?

 

[javaerd]

Ich weiss es nicht genau, als Ergebnis kommt für result = 1 raus.

    public static void binomialkoeffizient(){
       
        long result = 0;
        int n = 49;
        int k = 6;
       
        result = (n * faculty(n-1)) / ((faculty(k) * faculty(n-k)));
        System.out.println(result);
    }
   
    public static long faculty(int number){
        if(number < 0) return 0;
        if(number == 0) return 1;
        if(number == 1) return 1;
        return number * faculty(number-1);
    }

 

[JCODA]

49! also 49 Fakultät ist etwa im Größenbereich 10^62, das ist leider viel zu viel um ein einfaches long verwenden zu können. (long geht bis ca 10^19)

Entweder du verwendest BigInteger, oder du verwendest einen besseren Algorithmus um den Binomialkoeff auszurechnen.
Etwa die letzte Zeile in dieser Umformung:

 

[javaerd]

oka es hat mit BigInteger geklappt. Vielen dank!🙂

    public static void binomialkoeffizient(){
       
        BigInteger result = BigInteger.ONE;
        int n = 49;
        int k = 6;
       
        result = faculty(n).divide(faculty(k).multiply((faculty(n-k))));
        System.out.println(result);
    }
   
    public static BigInteger faculty(int number){
        if(number <= 1) return BigInteger.ONE;
        return BigInteger.valueOf(number).multiply(faculty(number-1));
    }
}