Die Fakultät in Java

Heute sprechen wir über Fakultäten und die gängigsten Möglichkeiten, die Fakultät (engl. factorial) zu bestimmen. Dies ist eine der grundlegendsten Funktionen, die ein Programmierer sowohl kennen als auch beherrschen muss. Also, fangen wir an. Die Fakultät der Zahl n, bezeichnet als n!, ist der Wert des Produkts (Multiplikation) aller natürlichen Zahlen von 1 bis n. So sieht das dann aus (zur Auffrischung deiner Mathekenntnisse): Außerdem gibt noch eine kleine Regel für 0: Wenn wir die Differenz zwischen 6! und 4! berechnen wollen: Schauen wir uns das Berechnen der Fakultät in Java einmal genau an (Java Fakultät Berechnen). Wir werden ein paar Möglichkeiten unter die Lupe nehmen, wie man in Java Berechnungen der Fakultät durchführen kann.

Gewöhnliche Lösung für ein Fakultätsprogramm (Fakultät in Java)

Hier ist ein einfaches Fakultätsprogramm mit Schleife:

class FactorialExample{  
 public static void main(String args[]){  
  int i,fact=1;  
  int number=7;// our number to do the necessary calculations in class Factorial    
  for(i=1;i<=number;i++){    
      fact=fact*i;    
  }    
  System.out.println("Factorial of "+number+" is: "+fact);    
 }  
}

Unsere Ausgabe auf der Konsole ist dann: Und noch ein erhellendes Beispiel:

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i; // finding factorial of number using loops
  }
  return result;
}

Das ist gar nicht schwer: Wir verwenden die übergebene Zahl als Größe unserer Schleife, in der wir mit allen vorherigen Zahlen multiplizieren, bis wir bei f ankommen. Und in main:

System.out.println(getFactorial(6) - getFactorial(4));

Wenn wir den Code testen, sehen wir, dass wir das gewünschte Ergebnis erhalten: 696.

Rekursive Lösung

Rekursion findet dann statt, wenn eine Methode sich selbst aufruft. Eine solche Methode wird als rekursive Methode bezeichnet. Sie besteht in der Regel aus zwei Teilen:

1. Einer Abbruchbedingung – wenn die Abbruchbedingung erfüllt ist, muss die Methode aufhören, sich selbst aufzurufen und beginnen, Werte nach oben durchzureichen. Denn wenn es keine Abbruchbedingung gibt, haben wir eine Endlosschleife, in der sich die Methode immer wieder selbst aufruft, bis wir einen StackOverflowError bekommen.
2. Welche Logik auch immer die Situation erfordert, plus einen rekursiven Aufruf, aber mit einem anderen Eingabewert.

Das Berechnen der Fakultät in Java ist ein perfektes Beispiel dafür, wann man Rekursion verwenden sollte:

public static int getFactorial(int f) { // finding factorial of number using recursive solution
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

Unsere Rekursionsabschlussbedingung tritt sein, wenn wir 1 erreichen. Wenn der Parameter nicht 1 ist, dann multiplizieren wir den aktuellen Wert mit dem Ergebnis des nächsten rekursiven Aufrufs der Methode (an den wir den aktuellen Wert minus 1 übergeben).

Lösung mit einem Stream

Wenn du mit der Stream-Funktionalität von Java noch nicht vertraut bist, oder wenn du dein Gedächtnis auffrischen möchtest, wirst du von der Lektüre dieses Abschnitts profitieren.

public static int getFactorial(int f) { // finding factorial of number using Stream 
  if (f <= 1) {
     return 1;
  }
  else {
     return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
  }
}

Hier verwenden wir die spezielle Klasse IntStream, die uns zusätzliche Möglichkeiten beim Arbeiten mit einem Strom von int-Werten bietet. Um einen solchen Stream zu erzeugen, verwenden wir seine statische Methode rangeClosed, die Werte von 2 bis einschließlich f in Schritten von 1 erzeugt. Als nächstes verwenden wir die Methode reduce, um alle Werte zu kombinieren. Genauer gesagt, zeigen wir der Methode, wie wir die Werte kombinieren wollen. Schließlich erhalten wir den resultierenden Wert mit der abschließenden Methode getAsInt.

BigInteger verwenden

In Java wird die Klasse BigInteger häufig verwendet, um Zahlen, insbesondere GROSSE Zahlen, zu verarbeiten. Wenn wir int verwenden, dann ist die maximale Fakultät, die wir ohne Datenverlust verarbeiten können, die der Zahl 31. Für den Datentyp long ist die maximale Fakultät die der Zahl 39. Was aber, wenn wir die Fakultät von 100 berechnen müssen? Passen wir die vorherigen Lösungen mit BigInteger an.

Gewöhnliche Lösung

public static BigInteger getFactorial(int f) { // finding factorial of number using BigInteger
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

Der Algorithmus ist im Wesentlichen derselbe, aber hier nutzen wir die Möglichkeiten von BigInteger: BigInteger.ONE ist der Startwert 1, und multiply() wird verwendet, um den vorherigen Fakultätswert und die aktuelle Zahl zu multiplizieren.

Rekursive Lösung

public static BigInteger getFactorial(int f) {
  if (f <= 1) {
     return BigInteger.valueOf(1);
  }
  else {
     return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
  }
}

Die allgemeine Logik der Lösung ändert sich nicht, außer dass einige Methoden für die Zusammenarbeit mit BigInteger hinzugefügt werden.

Lösung mit einem Stream

public static BigInteger getFactorial(int f) {
  if (f < 2) {
     return BigInteger.valueOf(1);
  }
  else {
     return IntStream.rangeClosed(2, f).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
  }
}

Hier ist im Wesentlichen alles gleich, aber mit BigInteger. Die Stream-Klasse stellt uns die Methode mapToObj bereit, mit der wir int-Werte in BigInteger umwandeln, um sie dann mit der multiply-Methode mit sich selbst zu multiplizieren (und get() wurde hinzugefügt, um ein Objekt aus dem Optional-Wrapper zu holen). Wenn wir eine dieser drei Methoden mit einem Argument von 100 ausführen, dann vermeiden wir einen Stapelüberlauf und erhalten das korrekte Ergebnis: