7.4.2 n! nichtrekursiv und rekursiv
 
n! In der Mathematik wird n! häufig definiert als das Produkt

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

 

Download:
FakultaetTest1.
java
 

Ein schon etwas anspruchvolleres Programm, das eine while-Schleife benutzt, ist das nächste Beispiel. Es zeigt, wie man die Fakultät einer Zahlberechnen.
import info1.*;
public class FakultaetTest1{
   public static void main(String[] args){
      System.out.print("n: ");
      int n = Console.in.readInt();
      System.out.println("n! = "+fak(n));
   }
   static int fak(int n){
      int fakultaet = 1;
      int faktor = 1;
      while (faktor <= n){
        fakultaet = fakultaet*faktor;
        //System.out.println(fakultaet);
        faktor++;
      }
      return fakultaet;
   }
}

Der Schreibtischtest verdeutlicht, was bei den einzelnen Programmschritten geschieht. Ein Schreibtischtest ist eine Tabelle, in die alle Variablen eingetragen und "Entwicklung" ihrer Werte verfolgt werden. Dabei entspricht eine Zeile der Tabelle, jeweils einem Schleifendurchgang

Initialisierungsdaten: faktor=1, fakultaet =1, n = 5 (z.B).

faktor in Bedingung Bedingung fakultaet vor der Zuweisung fakultaet nach der Zuweisung faktor
1 true 1 1 2
2 true 1 2 3
3 true 2 6 4
4 true 6 24 5
5 true 24 120 6
6 false      

 

Programmausgabe bei n=5 n: 5
1
2
6
24
120
n! = 120

 
n = 18 Wir wählen n = 18 und lassen uns die Zwischenergebnisse im Schleifenkörper ausgeben:
 
 
n: 18
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
479001600
1932053504
1278945280
2004310016
2004189184
-288522240
-898433024
n! = -898433024
Wir sehen, dass wegen des Minuszeichens in den letzten beiden Schleifendurchgängen Unsinn ausgegeben wird. Eine genauere Prüfung zeigt, dass schon vorher etwas 'faul' ist, dort nämlich, wo die Werte der Errechnenten Zwischenwerte der Fakultät sinken, satt steigen. Der Grund für die offensichtlich falsche Berechnung des Fakultät liegt nicht am Algorithmus, sondern an der Darstellung von int-Zahlen in Java. Tatsächlich ist der maximale Wert für int Zahlen: 2 147 483 647.  Wählen wir für die Variable fakultaet an Stelle des Typs int, den Typ long, können wir bis 20! die Fakultäten berechnen. Aber schon ab 21! reicht auch der Grunddatentyp long nicht mehr aus.
 

Die etwas modifizierte Methode hat folgende Gestalt.:
 

Downlaod:

FakultaetTest2. java


 

   static long fak(int n){
      long fakultaet = 1;
      int faktor = 1;
      while (faktor <= n){
        fakultaet = fakultaet*faktor;
        System.out.println(fakultaet);
        faktor++;
      }
      return fakultaet;
   }
  Die Definition n! = n . (n-1) . (n-2) . ... . 2 . 1 hat für die Puristen unter den Mathematikern den Nachteil, dass die drei Punkte für usw. stehen, also voraussetzen, dass der Leser wohl weiß, was gemeint sei. Dies ist aber kein mathematisch korrektes Vorgehen. Tatsächlich heißt die exakte Definition:

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

Wie wir sehen handelt es sich um eine rekursive Definition. Was liegt also näher, als diese Definition direkt als rekursive Methode zu implementieren?

 

Die rekursive Methode fakultaet(..)
   private static long fakultaet(int n){
      if (n==0) return 1;
      else return n*fakultaet(n-1);
   }
Download:
Mathematik.java
Wie wir sehen, ist der Quellkode nicht nur kürzer, sondern auch einfacher zu lesen. Ein Effizienzvergleich der nichtrekursiven mit der rekursiven Methode zeigt keinen Unterschied. Wegen der leichteren Lesbarkeit übernehmen wir die rekursive Methode in die Klasse Mathematik.
 
zu 7.4.3 Fibonacci-Zahlen
zur Startseite www.pohlig.de  (C) MPohlig 2006