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){
  if (a==1||a==2) return 1;
  else return fib(a-1)+fib(a-2);
}

Wir testen die Methode in einem kleinen Demo-Programm:

import info1.*;

public class FibonacciDemo{

  public static void main(String[] args){

    System.out.print("Geben Sie ein Zahl an: ");

    int a = Console.in.readInt();

    System.out.println("fib("+a+") = " + fibonacci(a));

  }

  private static int fibonacci(int a){

    if (a==1||a==2) return 1;

    else return fibonacci(a-1)+fibonacci(a-2);

  }

}

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:

FibonacciDemoUhr. java

StoppUhr.class

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.

import info1.*;
public class FibonacciDemoUhr{
  public static void main(String[] args){
    StoppUhr uhr = new StoppUhr();
    System.out.print("Geben Sie ein Zahl an: ");
    int a = Console.in.readInt();
    uhr.starten();
    int fib = fibonacci(a);
    uhr.stoppen();
    System.out.println("fib("+a+") = " + fib);
    System.out.println("Rechendauer: "+ uhr);
  }
  private static int fibonacci(int a){
    if (a==1||a==2) return 1;
    else return fibonacci(a-1)+fibonacci(a-2);
  }
}

Damit wir vernünftig die Rechenzeit messen können, darf der Rekursive Aufruf nicht erst in der Ausgabe erfolgen, sonder vorher. Dann muss aber das Ergebnis in einer Variablen gespeichert werden, im Quelltext ist dies
fib vom Typ int. Mit der Methode fibonacci(int a), die Fibonacci-Zahlen rekursiv berechnet, haben wir eine leicht zu durchschauende Methode, wir erkaufen dies durch lange Rechenzeiten. Dass das nicht immer so ist, haben wir bei der rekursiven Methode zur Berechnung des ggT zweier Zahlen mit dem erweiterten Euklidschen Algorithmus gesehen. Im nächsten Abschnitt suchen wir nach einer effizienteren Methode Fibonacci-Zahlen zu berechnen.   In den Hausaufgaben schließlich wird ein noch effizienterer Algorithmen zur Berechnung von Fibonacci-Zahlen vorgestellt und mit den zuvor vorgestellten verglichen.
 

zu 15.8 Fiboinacci-Zahlen nicht rekursiv
zur Startseite www.pohlig.de  (C) MPohlig 2004