15.7 Fibonacci-Zahlen rekursiv bestimmen |
|
Fibonacci-Zahlen | Wir haben
gesehen, dass die Fibonacci-Zahlen folgende Gestalt haben 1, 1, 2, 3, 5, 8, 13, 21, ... Wir haben weiter gesehen, dass ein Folgenglied sich dadurch berechnet, dass man seine beiden Vorgänger addiert. Damit dies funktioniert, muss man allerdings wissen, welche Werte die beiden ersten Glieder haben. Die exakte Formulierung der Fibonacci-Folge geschieht durch das folgende Bildungsgesetz: fib(n) = fib(n-1) + fib(n-2) mit fib(1) = fib(2) = 1 Deutlich wird die rekursive Art der
Definition dieser Zahlenfolge. Diese Definition lässt sich nahezu eins zu
eins in einen Java-Quellcode übersetzen: |
FibonacciDemo. java | public static
long fib(int a){ Wir testen die Methode in einem kleinen Demo-Programm:
Schauen wir uns die Methode etwas genauer an und fragen uns, was genau passiert denn eigentlich, wenn wir fib(5) bestimmen lassen? Bevor fib(5) bestimmt werden kann, werden die Aufrufe fib(4) und fib(3) abgearbeitet, wobei z.B. fib(3) erst wieder fib(2) und fib(1) aufrufen, die aber jeweils 1 zurückgeben. Wir können uns das Vorwärtsschreiten in einer Grafik vorstellen, wo bei wir bei f(6) anfangen und den Pfeilen folgen. Die Regel dabei ist, folge den Pfeilen wenn möglich nach unten und erst wenn kein Pfeil mehr nach unten zeigt, nehme man die Alternative. Dabei beachte man, dass einem Pfeil nur einmal gefolgt wird. Der erste Teil der Aufruffolge ist also: fib(5) -> fib(4) -> fib(3) -> fib(2), liefert Wert 1. Zurück zu fib(3) weiter auszuwerten fib(3) -> fib(1), liefert 1, zurück an fib(3), fib(3) gibt an fib(4) den Wert 2. Nun kann fib(4) weitermachen, denn es braucht noch fib(2), die 1 zurückliefert. Nun kann fib(4) den Wert 3 an fib(5) liefern, fib(5) benötigt aber noch fib(3) usw. Deutlich wird: Es entsteht ein komplexe Aufruffolge der Methode und es wird die Methode recht häufig mit den gleichen Parametern aufgerufen, was die Effizienz des Algorithmus schwer beeinträchtigt. Eine nicht rekursive Methode wäre wesentlich schneller und würde weniger Speicherplatz benötigen. Deutlich wird die Problematik, wenn z.B. fib(1000) bestimmen wollte. (vgl. dazu auch die Hausaufgaben)
|
Download: |
Lassen wir die Fibonacci - Zahl fib(40) = 102334155 berechnen,
dauert es eine geraume Zeit, bis das Ergebnis erscheint. Dies wundert uns
nicht, denn das mehrfache, i.P. überflüssige Berechnen von
Zwischenergebnissen kostet Ressourcen und Zeit. Um die genaue Rechendauer,
sie hängt natürlich vom Rechner ab, bauen wir in unser DemoProgramm eine
Uhr ein.
|
zu | 15.8 Fiboinacci-Zahlen nicht rekursiv |
zur Startseite | www.pohlig.de (C) MPohlig 2004 |