In der Informatik kann man sich mit einem Teilgebiet, der Algorithmik, beschäftigen. Das hört sich eigentlich trocken und langweilig an: Algorithmen sind Ausführungsvorschriften, die bestimmte Verfahren beschreiben. Beispielsweise Verfahren, mit denen eine Liste von Namen sortiert werden kann. Oder ein Verfahren, durch dessen Hilfe man Zahlen schriftlich addieren kann:

Das ist ein relativ einfaches Beispiel, an dem man nicht sehen kann, wie wichtig ein effizienter Algorithmus für ein Problem ist. Deshalb widme ich mich hier einem relativ einfachen Anfängerbeispiel, an dem man genau das sehr gut sehen kann: den Fibonacci-Zahlen und deren Berechnung.

Fibonacci-Zahlen

Die Fibonacci-Zahlen sind nicht nur als eindrucksvolles Beispiel hervorragend geeignet, sondern sind auch noch als Forschungsgebiet an sich sehr interessant: sie laufen einem in der Informatik ständig wieder über den Weg: die ggT-Berechnung nach dem euklidischen Algorithmus beispielsweise nimmt ihr Worst-Case-Verhalten (also die Zahlen, für die der Algorithmus am langsamsten ist) genau bei Anwendung auf zwei Fibonacci-Zahlen an. Auch haben die Fibonacci-Zahlen eine verblüffende Beziehung zum goldenen Schnitt, auf die ich später eingehen werde. Eigentlich "erfunden" wurden sie aber aus einem eher praktisch orientierten Problem: man nimmt an, man hätte ein Paar neugeborener Kaninchen. Dieses Paar wird nach zwei Monaten geschlechtsreif und bekommt ab diesem Zeitpunkt jeden Monat ein weiteres Paar. Für die Nachfahren gelten dieselben Regeln: diese werfen auch nach zwei Monaten das erste Paar Nachkommen, dessen Nachkommen wiederum und so weiter. Wenn man ideale Bedingungen für die Kaninchen annimmt (unbegrenzte Lebenszeit der Kaninchen und genügend Futter) gilt es nun zu bestimmen, wieviele Kaninchen die Herde insgesamt nach n Monaten hat.

Die Rekursionsformel

Rekursion bedeuted, dass ein bestimmtes Problem auf ein oder mehrere kleine Teilprobleme zurückgeführt wird. Programmiertechnisch nennt man Rekursion den Vorgang, wenn eine Funktion sich selbst wieder (mit veränderten Parametern) aufruft. Hier die Formel für die Fibonacci-Zahlen, die relativ einfach zu verstehen ist:

Ansatz 1: Naive Rekursion

Der erste, naive Ansatz ist, das Problem einfach so zu programmieren, wie es gegeben ist: man ersetzt jeweils, wenn in einem Ausdruck der Form f_n n nicht 0 oder 1 ist, f_n durch "f_n-1 + f_n-2". In einer Programmiersprache (hier C) sieht das dann so aus:

int fib_rek(int n) {
    if (n==0) return 0;
    if (n==1) return 1;

    return fib_rek(n-1)+fib_rek(n-2);
}

Das Problem wird also schrittweise reduziert. Allerdings wird für große "n" der Rechenaufwand unerträglich, denn der Computer muss unglaublich viele Rechnungen doppelt ausführen:

In Baumstruktur wird schnell deutlich, dass hier eine kaskadenartige Rekursion auftritt, die exponentiellen Aufwand hat; die Basisfälle (f₀ und f₁) sind in dem Diagramm fett gezeichnet. Weiterhin erkennt man deutlich, dass bereits berechnete Zwischenergebnisse jedes Mal wieder erneut berechnet werden; f₃ wird beispielsweise zweimal, f₂ viermal ausgerechnet:

Mit diesem Verfahren benötigt man also eine in Abhängigkeit von "n" exponentiell wachsende Anzahl an Additionen; wieviele genau, dafür kann man eine Formel herleiten, was am Ende dieses Textes auch gemacht wird.

Ansatz 2: Lineare Iteration

Nun ist eine Aufgabe der Algorithmik, sich mit Verfahren zu beschäftigen, die den Algorithmus verbessern können. Und eine Methode ist schon offensichtlich: man geht die Zahlen durch und merkt sich jeweils nur die letzten zwei. Dadurch reduziert sich die Anzahl an Additionen drastisch. Für die Basisfälle f₀ und f₁ sind wie auch in der naiven Rekursion gar keine Additionen notwendig. Für jede Zahl, die größer als 1 ist, benötigt dieser Algorithmus "n-1" Additionen. Die Anzahl an Additionen steigt also linear mit der Problemgröße "n". Hier ein Ansatz für eine mögliche Implementierung:

int fib_iter(int n) {
    int a, b, c;
    int i;
    int sum;

    if (n==0) return 0;
    if (n==1) return 1;

    a=0;
    b=1;
    c=0;
    sum=0;
    for (i=2; i<=n; i++) {
        c = a + b;
        a = b;
        b = c;
    }

    return c;
}

Ein Vergleich der naiven Rerkursion mit der linearen Iteration, bei dem für die Zeitberechnungen angenommen werden soll, dass ein Computer eine Milliarde Additionen in einer Sekunde bewerkstelligen kann:

Und hier abgetragen der tatsächliche Zeitaufwand für die oben angegebenen Implementierungen auf meinem PC:

Man kann also deutlich sehen, dass die iterative Variante quasi keine Zeit im Vergleich zur rekursiven Variante benötigt; die 2ms werden wohl hauptsächlich für die Programminitialisierung verwandt, der eigentliche Rechenaufwand fällt nicht ins Gewicht.

Ansatz 3: Geschlossene Form

Zunächst soll der goldene Schnitt betrachtet werden, ein Problem, dass scheinbar mit den Fibonacci-Zahlen recht wenig zu tun hat. Der goldene Schnitt ist definiert dadurch, dass sich a zu b verhält wie die Summe von a und b zu a. Dies drückt folgende Formel aus:

Durch Auflösen nach x nach der quadratischen Lösungsformel kommt man zu zwei Lösungen, die im Folgenden als Phi und Phi-Dach bezeichnet werden:

Nun sei einfach behauptet, dass die n-te Fibonacci-Zahl durch folgende Formel errechnet werden könnte:

Für diese Ausführungen genügt es, dass die Formel einfach vom Himmel fällt und wir beweisen können, dass sie auch stimmt. Die Herleitung ist etwas komplizierter. Für die Interessierten seien hier nur folgende Stichworte genannt, mit denen man bei Google sicher weiter kommt: erzeugende Funktion von f_n finden, Partialbruchzerlegung machen, also eine Z-Transformation durchführen, siehe auch allgemeine Lösung C-rekursiver Folgen.

Nun weiter zur oben genannter Formel. Wir beweisen diese durch vollständige Induktion, ein Beweisverfahren, das vielleicht in der Schule schon einmal angewandt wurde. Der Induktionsanfang:

Für f₀ und f₁ stimmen die Werte also. Wir berechnen nun f_n-1+f_n-2:

Wir nutzen nun zweimal die Tatsache aus, dass Phi sowie Phi-Dach Lösungen der Gleichung des goldenen Schnitts, sind. Es gilt also, dass Phi² = Phi+1 und PhiDach² = PhiDach+1. Dies berücksigend werfen wir in einer Nebenrechnung einen Blick auf den Term Phi^-1 + Phi^-2:

Wir sehen, dass der Term 1 ergibt. Für PhiDach wird dies nicht explizit gezeigt, sämtliche Schritte sind absolut analog: denn auch PhiDach genügt der Gleichung des goldenen Schnitts. Nun setzen wir die in der Nebenrechnung gewonnenen Erkenntnisse in die Gleichung 2 ein:

Und schon steht die Lösung da! Wir haben soeben also bewiesen, dass die Formel stimmt. So können wir für sämtliche Werte für "n" die Lösung sofort berechnen, da wir eine geschlossene Form haben.

Zurück zur Kaskadenrekursion

Um noch einmal auf die Kaskadenrekursion zurückzukommen, die als erster Ansatz gewählt wurde: Oben habe ich geschrieben, dass ich hier auf die Formel eingehen werde, mit der man bestimmen kann, wie viele Additionen zur Berechnung der n-ten Fibonacci-Zahl notwendig sind. Erstaunlicherweise ähnelt diese Gleichung der Fibonacci-Gleichung erstaunlich. Man kann auf die geschlossene Form kommen, indem man die Schritte absolut analog zur Herleitung der geschlossenen Form der Fibonacci-Zahlen anwendet. Denn die Aufwandsfunktion genügt folgender Rekursionsgleichung:

Ohne Beweis der Korrektheit sei hier die Lösung präsentiert:

Also ist der Aufwand, um die n-te Fibonacci-Zahl nach dem Verfahren der naiven Rekursion zu berechnen genau um eins weniger als die n+1-te Fibonacci-Zahl selbst!

Schlusswort

Hier wurde jetzt also gezeigt, dass es sich durchaus lohnen kann, ein bischen Zeit in einen Algorithmus zu investieren, damit hinterher eine ungleich bessere Lösung herauskommt. Auch wurde sicherlich deutlich, dass die guten Lösungen für Probleme keineswegs offensichtlich sind, sondern dass deren Herleitung oft höhere Mathematik benötigt. Dennoch ist es wichtig, so wissen, dass viele Algorithmen verbessert werden können; Schließlich hat nicht jeder ein Paar Tausend Jahre Zeit, um sich die hundertste Fibonacci-Zahl anzeigen zu lassen...