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 |
|
Download:
|
Tauschen
wir die rekursive Methode durch eine nicht rekursive aus, so bekommen wir
FakultaetDemo2.
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: |
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:
|
|
|
Download: Fakultaet DemoZeit.java Fakultaet Demo2Zeit.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 |