14.2 Fakultät
 
n! In der Mathematik wird n! häufig definiert als das Produkt

n . (n-1) . (n-2) . ... . 2 . 1

Nach dieser Definition haben wir bereits eine Klasse implementiert, die die Fakultät einer Zahl n bestimmt. (vgl. dazu 11.2.1). Diese Definition hat den Nachteil, dass die drei Punkte für usw. stehen, also voraussetzen, dass der Leser wohl wisse, was gemeint sei. Dies ist aber kein mathematisch korrektes Vorgehen. Tatsächlich heißt die exakte Definition:

0! = 1 und n! = n. (n-1)!

Es handelt sich also um eine rekursive Definition. Was liegt also näher, als diese Definition direkt in einer Methode zu implementieren?

 

Download:
Faultaet Demo.java
import info1.*;
public class FakultaetDemo {

   public static void main (String[] args) {
       System.out.print("n: ");
       int n = Console.in.readInt();
       System.out.println("n! = "+fakultaet(n));
   }
   private static long fakultaet(int n){
      if (n==0||n==1) return 1;
      else return n*fakultaet(n-1);
   }
}
Download:

Fakultaet Demo2.java

 

Tauschen wir die rekursive Methode durch eine nicht rekursive aus, so bekommen wir FakultaetDemo2.
import info1.*;
public class FakultaetDemo2{
   public static void main(String[] args){
      System.out.print("n: ");
      int n = Console.in.readInt();
      System.out.println("n! = "+fakultaet(n));

   }
   private static long fakultaet(int n){
      long fakultaet = 1;
      int faktor = 1;
      while (faktor <= n){
        fakultaet = fakultaet*faktor++;
      }
      return fakultaet;
   }
}

Wenn man beide Varianten von fakultaet(int n) miteinander vergleicht, so gewinnt  die rekursive Variante wegen Eleganz und Durchsichtigkeit (vorausgesetzt man hat mit Rekursionen keine grundsätzlichen Schwierigkeiten).

 

Effizienz

Download:
StoppUhr. class

Die Diskussion über die verschiedene ggT-Algorithmen hat uns für die Frage nach der Effizienz von Algorithmen sensibilisiert. Wir wollen wissen, ob beide Varianten von fakultaet(int n) gleich oder unterschiedlich effizient sind. Dazu benutzen wir unsere schon bei der Untersuchung der ggT-Algorithmen verwendeten StoppUhr.

Die main-Methoden in den beiden Demo-Programmen FakultaetDemo und FakultaetDemo2 waren gleich und werden durch die folgende Methode ersetzt:

 

 
public static void main (String[] args) {
   StoppUhr stoppUhr1 = new StoppUhr();
   System.out.print("n: ");
   int n = Console.in.readInt();
   stoppUhr1.starten();
   long fakt = fakultaet(n);
   stoppUhr1.stoppen();
   System.out.println("n!="+fakt+"  RechenZeit: "+stoppUhr1);
}
Download:

Fakultaet
DemoZeit.java


Fakultaet Demo2Zeit.java

Mathematik. java

Das Experiment zeigt zwischen beiden Methoden fakultaet(int n) keinen Unterschied. Es werden tatsächlich 0,0 Sekunden angezeigt. Größere Werte für 'n' als die Zahl 20 können wir nicht wählen, da unsere Programme keine korrekte Ergebnisse mehr liefern kann; das hat nichts mit dem Algorithmus sondern mit dem für die Rückgabe gewählten Datentyp (siehe Hausaufgaben). Wenn man den Quelltext der beiden Methoden betrachtet, erkennt man, dass die Anzahl der Schleifendurchgänge bei der nichtrekursiven Methode 'n', und damit gleich der Rekursionstiefe der alternativen Methode ist. Beide Varianten sind also gleich effizient. Wegen der leichteren Lesbarkeit nehmen wir die rekursive Variante der Methode in unsere Klasse Mathematik auf und ändern natürlich das private zu public.
Dass rekusive Methoden häufig leichter lesbar sind als ihre nichtrekursive Alternativen haben wir gesehen. Nicht selten sind sie aber deutlich ineffizienter; dies zeigt das Beispiel der Berechnung von Fibonacci-Zahlen.
 
zu 14.3 Fibonacci
   
zur Startseite www.pohlig.de  (C) MPohlig 2003