Meta-Beispiel: Die Fibonacci-Funktion
Die Fibonacci-Funktion gehört zu den am Häufigsten verwendeten Programmierbeispielen. Sie bildet den Index n auf das n-te Element der Fibonacci-Folge ab. Aufgrund der allgemein bekannten, mathematischen Definition ist sie für Programmieranfänger leicht verständlich – sowohl bezüglich der Anforderung als auch der Realisierung.
Doch es gibt auch schlechte Eigenschaften, die mich an ihrer Eignung für solche Beispiele zweifeln lassen. Aus meiner Sicht ist eine wichtige Frage, welches Bild man Anfängern von Programmiersprachen vermitteln möchte. Die Fibonacci-Funktion enthält zahlreiche versteckte und unerwünschte Aussagen. Für mich ist sie daher ein Meta-Beispiel um darauf aufmerksam zu machen, dass viele Beispiele in ihren Aussagen irreführend sind.
Programmiersprachen sind beschränkt.
Es fängt bereits mit der Signatur der Funktion an. Welche Typen sind für Parameter und Rückgabewert geeignet? Entscheidet man sich in Java für einen long, so kann man gerade noch die 92. Fibonacci-Zahl repräsentieren. Verwendet man dagegen den Typ BigInteger, so ist die Komplexität der Implementierung Anfängern kaum noch zu vermitteln.
long fibonacci(int n);Programmiersprachen sind langsam.
In C, C++ oder Java sieht ein typisches Fibonacci-Beispiel wie folgt aus. Der Wert der Funktion wird rekursiv berechnet – entsprechend ihrer mathematischen Definition. Die Verwendung als Beispiel suggeriert eine gewisse Qualität der Implementierung. Tatsächlich ist sie jedoch denkbar ungeeignet, da die Laufzeit exponentiell zum Index steigt.
long fibonacci(int n) {
return n > 1 ? fibonacci(n - 2) + fibonacci(n - 1) : n;
}Als C++-Funktion benötigt die Implementierung mit Clang bei aktivierten Optimierungen für n=40 bereits 0,7 Sekunden auf meinem Rechner. GCC optimiert rekursive Funktionen ein wenig aggressiver und benötigt dagegen nur 0,4 Sekunden. Für n=50 liegen die Laufzeiten bei 95,2 und 46,7 Sekunden, und für n=92 benötigt man viel Geduld.
Programmiersprachen sind ausdrucksschwach.
Das Laufzeitproblem ließe sich durch eine imperative Implementierung einfach lösen, wenn die typischen Programmiersprachen ein wenig ausdrucksstärker wären. Es ist interessant, welche Schwächen die Fibonacci-Funktion aufdeckt, und wie umständlich eine funktionierende Implementierung in C, C++ und Java ist. Das folgende Listing enthält eine Kombination aus C++, Missbrauch von Sprachkonstrukten und einer nicht unterstützten Tuple-Zuweisung, um ein optisch ansehnliches Ergebnis zu erzielen.
long fibonacci(int n) {
long a = 0, b = 1;
while (n --> 0) // repeat n times
a, b = b, a + b; // ERROR: unsupported tuple assignment
return a;
}Wenn man die Tuple-Zuweisung durch eine Dreieckszuweisung über eine lokale Variable ersetzt, so lässt sich die Funktion tatsächlich in C++ übersetzen. Damit erfolgt die Berechnung der 92. Fibonacci-Zahl im Bruchteil einer Sekunde.
Programmiersprachen sind unverständlich.
Die beiden Implementierungen könnten den Eindruck erwecken, dass rekursive Funktionen verständlicher und imperative Funktionen effizienter sind. Dem ist jedoch nicht so. Das folgende Listing zeigt eine rekursive Implementierung in C++, die genauso effizient wie die imperative Implementierung ist.
long fibonacci(int n, long a = 0, long b = 1) {
return n > 0 ? fibonacci(n - 1, b, a + b) : a;
}Tatsächlich ist es so, dass sowohl GCC als auch Clang die Rekursion wegoptimieren (mit der sogenannten Tail Call Elimination), und für die beiden Implementierungen beinahe identischen Maschinencode generieren. Doch gewonnen ist dadurch nichts: Diese Version ist nicht nur genauso effizient sondern mindestens auch genauso unverständlich wie die vorherige Version.
Fazit
Es bleibt also die Einsicht: Egal wie man es macht, das Fibonacci-Beispiel zeigt vor allem Schwächen typischer Programmiersprachen. Anfängern sollte man hingegen vermitteln, wie einfach moderne Programmiersprachen sind. Doch dafür werden bessere Beispiele benötigt.