Eine Funktion zur Berechnung der Fibonacci-Zahlen schreiben – Diese recht beliebte Aufgabe wird gerne von Uni-Professoren und Berufsschullehrern von Fachinformatikern gestellt. Die Gr\u00fcnde liegen auf der Hand: Anhand einer \u00fcberschaubaren Logik l\u00e4sst sich die Funktionsweise von Rekursion demonstrieren. Und au\u00dferdem Ihre Nachteile, da die rekursive Berechnung gr\u00f6\u00dferer Fibonacci-Zahlen rechenintensiv ist. Folgender Artikel zeigt die Umsetzung einer einfachen Konsolenanwendung in der Programmiersprache C zur Berechnung dieser Zahlen.<\/p>\n
Kurz gesagt dient sie zur Berechnung von Wachstumsvorg\u00e4ngen. Etwas detaillierter l\u00e4sst sie sich an folgendem Beispiel erkl\u00e4ren: Angenommen, die Kaninchen in einem Stall erhalten jeden Monat zwei gegengeschlechtliche Zwillinge als Nachwuchs. Unter der Annahme, dass die Kaninchen niemals sterben oder aufh\u00f6ren sich weiter fortzupflanzen, entspricht die Anzahl der Kaninchenpaare im Stall nach n Monaten die n-te Fibonacci-Zahl – in unserem Beispiel mit der Funktion F(n).<\/p>\n
Haben wir zu Beginn nur ein einzelnes Paar Kaninchen, ver\u00e4ndert sich der Bestand in den ersten beiden Monaten nicht: F(1) = 1 und F(2) ist ebenfalls 1 – denn dieses Paar wird erst nach dem Alter von zwei Monaten zeugungsf\u00e4hig sein. Im dritten Monat (n = 3) wird ein weiteres Kaninchen gezeugt, sodass nun insgesamt 2 Paare (Jeweils 1 Paar Eltern und Kinder) vorhanden sind – F(3) ergibt daher 2. Nachdem vierten Monat leben F(4) = 3 Paare, das zweite Zwillingspaar der Eltern.<\/p>\n
Nun wird es interessant: Im 5. Monat bekommt nicht nur das urspr\u00fcnglich erste Paar Nachwuchs, sondern auch\u00a0deren erste Kinder\u00a0– Somit leben nun 5 Kaninchen. Monat 6 bring insgesamt drei neue Paare, da hier zu den eben genannten noch das zweite Nachwuchspaar dazu kommt. So setzt sich das Wachstum weiter fort.<\/p>\n
Die Anzahl der lebenden Paare im Monat n + 1 entspricht allgemein gesagt der Anzahl der Paare, die im vorherigen Monat (n) gelebt haben. Dazu werden die neu geborenen Addiert. Durch die Fortpflanzung alle zwei Monate ist die Anzahl der Kinder gleich wie die Anzahl der Paare, welche vor zwei Monaten lebten. Daraus l\u00e4sst sich die Formel<\/p>\n
\r\nf(n) = f(n - 1) + f(n - 2)\r\n<\/pre>\nableiten. Wobei diese nur gilt, wenn n gr\u00f6\u00dfer oder gleich 2 ist – Denn in den ersten beiden Lebensmonaten wird kein Nachwuchs gezeugt. f(1) ist somit 1 und f(2) = 2. Negative Fibonacci-Zahlen kann es nicht geben. Der Prototyp einer Funktion zur Implementierung dieser Formel k\u00f6nnte daher wie folgt aussehen:<\/p>\n
\r\nint calculate_fibonacci_number(int number);\r\n<\/pre>\nDie ganze Zahl number<\/strong> entspricht unserem Eingangswert n<\/strong>. Als R\u00fcckgabewert wird die ebenfalls ganzzahlige Fibonacci-Zahl geliefert. In der Funktion m\u00fcssen wir zun\u00e4chst mit If-Abfragen die oben genannten Ausnahmef\u00e4lle abfangen:<\/p>\n
\r\n\/\/ Von 0 bis 2 entspricht die Fibonacci-Zahl der Eingabe\r\nif (number >= 0 && number < 2) {\r\n\treturn number;\r\n}\r\n\r\n<\/pre>\nNun gelangen wir zur eigentlichen Berechnung der Fibonacci-Zahl. Die Implementierung gleicht dabei obiger Formel:<\/p>\n
\r\nreturn calculate_fibonacci_number(number - 1) + calculate_fibonacci_number(number - 2);\r\n<\/pre>\nDie gesamte Funktion sieht daher so aus:<\/p>\n
\r\nint calculate_fibonacci_number(int number) {\r\n\t\/\/ Von 0 bis 2 entspricht die Fibonacci-Zahl der Eingabe\r\n\tif (number >= 0 && number < 2) {\r\n\t\treturn number;\r\n\t}\r\n\treturn calculate_fibonacci_number(number - 1) + calculate_fibonacci_number(number - 2);\r\n}\r\n<\/pre>\nMit einem einfachen Beispielprogramm l\u00e4sst sich die Funktion auf vom Benutzer eingegebene Zahlen anwenden:<\/p>\n
\r\n\/\/ Beinhaltet Funktionen zur Ein- und Ausgabe wie printf und scanf - Der Name steht f\u00fcr StandardInputOutput\r\n#include <stdio.h>\r\n\/\/ In C m\u00fcssen die Prototypen getrennt von der Implementierung definiert werden. Bei gr\u00f6\u00dferen Anwendungen verschiebt man diesen Teil in eine Header-Datei (*.h)\r\nint calculate_fibonacci_number(int number);\r\n\r\nint main(void) {\r\n\tprintf("Fibonacci-Zahl berechnen\\n\\nBitte eine Zahl groesser 0 eingeben: ");\r\n\tint input_number = 0;\r\n\tscanf_s("%d", &input_number);\r\n\r\n\t\/\/ Eingegebene Zahl validieren und falls diese ung\u00fcltig ist den Nutzer zur erneuten Eingabe auffordern\r\n\tif (input_number < 0) { system("cls"); printf("Fehler: Die Fibonacci-Zahl kann nur von ganzen Zahlen berechnet werden, die gr\u00f6\u00dfer als 0 sind! Bitte Eingabe wiederholen."); main(); } \/\/ Ist die Eingabe g\u00fcltig, berechnen wir die dazugeh\u00f6rige Fibonacci-Zahl und geben sie aus int fibonacci_number = calculate_fibonacci_number(input_number); printf("Die Fibonacci-Zahl von %d lautet: %d\\n\\nBeliebige Taste zum beenden druecken...", input_number, fibonacci_number); getch(); } \/\/ Die eigentliche Implementierung der Funktion, die unsere Fibonacci-Zahl berechnet int calculate_fibonacci_number(int number) { \/\/ Von 0 bis 2 entspricht die Fibonacci-Zahl der Eingabe if (number >= 0 && number < 2) {\r\n\t\treturn number;\r\n\t}\r\n\treturn calculate_fibonacci_number(number - 1) + calculate_fibonacci_number(number - 2);\r\n}\r\n\r\n<\/pre>\n[box type=“info“ align=“aligncenter“ ]Zu beachten ist, dass diese Implementierung Windows-Spezifische Aufrufe wie cls<\/strong> verwendet. Sie sollten in dieser Form nur zu Lernzwecken verwendet werden – denn ein Angreifer k\u00f6nnte die Umgebungsvariablen manipulieren und dadurch ggf. Schadcode mit erh\u00f6hten Rechten ausf\u00fchren. Siehe dazu Sicherheitsl\u00fccken von Umgebungsvariablen<\/a>[\/box]<\/p>\n
Rekursive vs. iterative L\u00f6sung im Vergleich<\/h3>\n
Im obigen Beispiel wird die Fibonacci-Zahl rekursiv berechnet. Die Funktion\u00a0calculate_fibonacci_number<\/strong> ruft sich also selbst auf, um beispielsweise die vorherige Zahl zu berechnen. Diese L\u00f6sung ist wie man sieht sehr einfach und besteht nur aus einer Zeile Code. Rekursive Funktionen bringen allerdings zwei Probleme: Als Entwickler muss man penibel auf die Abbruchbedingung achten, um nicht in einer Endlosschleife zu landen. Vor allem bei komplexeren Funktionen wird dies schnell \u00fcbersehen bzw. nicht vollst\u00e4ndig eingebaut. Dar\u00fcber hinaus erzeugen rekursive Aufrufe zus\u00e4tzlichen Overhead, sodass diese L\u00f6sungen nicht selten eine schlechtere Performance aufweisen als iterative Ans\u00e4tze.<\/p>\n
\r\n\/\/ Die eigentliche Implementierung der Funktion, die unsere Fibonacci-Zahl berechnet\r\nint calculate_fibonacci_number_iterativ(int number) {\r\n\t\/\/ Von 0 bis 2 entspricht die Fibonacci-Zahl der Eingabe\r\n\tif (number >= 0 && number < 2) {\r\n\t\treturn number;\r\n\t}\r\n\r\n\tint fibonacci_number, \r\n\t\tlast_fibonacci_number = 0, \r\n\t\tpenultimate_fibonacci_number = 1;\r\n\t\/\/ Alle Fibonacci-Zahlen von 1 bis zur \u00fcbergebenen Zahl m\u00fcssen berechnet werden\r\n\tfor (int i = 1; i < number; i++) {\r\n\t\t\/\/ Sie setzt sich aus der Summe der letzten und vorletzten Fibonacci-Zahl zusammen\r\n\t\tfibonacci_number = last_fibonacci_number + penultimate_fibonacci_number;\r\n\t\t\/\/ Nach jedem Durchlauf rutschen die Zahlen eines weiter nach hinten: Die aktuelle wird zur letzten und die letzte zur Vorletzten\r\n\t\tlast_fibonacci_number = penultimate_fibonacci_number;\r\n\t\tpenultimate_fibonacci_number = fibonacci_number;\r\n\t}\r\n\treturn fibonacci_number;\r\n}\r\n<\/pre>\nBei kleineren Zahlen ist der Unterschied derart gering, dass er bedenkenlos vernachl\u00e4ssigt werden kann. Werden jedoch gr\u00f6\u00dfere Zahlen berechnet, macht sich der Overhead bemerkbar: Die Fibonacci-Zahl zu 35 wird rekursiv in 840 ms berechnet. Bei 40 als Input sind es schon rund 9,4 Sekunden. Berechnen wir die Fibonacci-Zahl von 42, ben\u00f6tigt die rekursive Variante\u00a0mehr als satte 24 Sekunden. Die iterative L\u00f6sung dagegen ist derart schnell, dass ihre Ausf\u00fchrungszeit in Millisekunden nicht messbar ist – Sie liegt wohl im Nanobereich.<\/p>\n