Quick wins for a faster PC:
Scan for outdated or missing drivers - takes under a minuteDriver Scan →Repair Windows errors before they cause bigger problemsFix Now →iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more
Die Fibonacci-Folge ist eine Zahlenfolge, in der jedes neue Glied aus der Summe der beiden vorherigen entsteht. In der heute häufig verwendeten, 0-basierten Schreibweise beginnt sie mit 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 und so weiter.
Für die Informatik ist die Folge besonders nützlich, weil sie ein leicht verständliches Beispiel für Rekursion, dynamische Programmierung, Laufzeitprobleme und mathematische Folgen liefert. Wichtig ist dabei die Indexierung: Manche Darstellungen beginnen mit F0 = 0, andere mit F1 = 1.
| # | Preview | Product | Price | |
|---|---|---|---|---|
| 1 |
|
The Golden Ratio: The Divine Beauty of Mathematics | $37.70 | Buy on Amazon |
| 2 |
|
Fibonacci Fractals : Coloring and Puzzles Book | $8.49 | Buy on Amazon |
| 3 |
|
Growing Patterns: Fibonacci Numbers in Nature | $7.99 | Buy on Amazon |
| 4 |
|
Fibonacci Numbers (Dover Books on Mathematics) | $9.25 | Buy on Amazon |
| 5 |
|
Blockhead: The Life of Fibonacci | $15.08 | Buy on Amazon |
Definition der Fibonacci-Folge
Die klassische Fibonacci-Folge wird rekursiv definiert:
What’s actually slowing this PC down?
Pick the symptom - the matching free tool is one click away.
F0 = 0F1 = 1Fn = Fn-1 + Fn-2 für n ≥ 2
Aus den beiden Anfangswerten werden die weiteren Zahlen berechnet:
#1 Best Overall
Index n |
Fibonacci-Zahl Fn |
Berechnung |
|---|---|---|
| 0 | 0 | Startwert |
| 1 | 1 | Startwert |
| 2 | 1 | 0 + 1 |
| 3 | 2 | 1 + 1 |
| 4 | 3 | 1 + 2 |
| 5 | 5 | 2 + 3 |
| 6 | 8 | 3 + 5 |
Beispielsweise gilt in dieser Schreibweise:
F6 = F5 + F4 = 5 + 3 = 8.
0-basierte und 1-basierte Schreibweise
Die Folge beginnt nicht in jeder Quelle an derselben Stelle. In der 0-basierten Schreibweise lauten die Startwerte:
F0 = 0 und F1 = 1.
Eine ebenfalls etablierte 1-basierte Schreibweise verwendet:
F1 = 1 und F2 = 1.
Dann lautet der Anfang 1, 1, 2, 3, 5, 8, 13. Beide Varianten beschreiben dieselbe Zahlenfolge; nur die Nummerierung ist verschoben. Vor einer Rechnung oder einer Programmieraufgabe sollte daher klar sein, welche Konvention gilt.
Windows Errors? Fix Them Before They Spread
Repair common Windows errors and clear accumulated junk for a smoother, more stable PC - no reinstall needed.Free scan · no reinstallOutdated Drivers Are Slowing You Down
One free scan finds every outdated or missing driver and matches the right update for your exact hardware.Free scan · exact hardware matchDer häufige Satz „Die Fibonacci-Folge beginnt mit 1, 1“ ist also nicht grundsätzlich falsch. Für Algorithmen und viele mathematische Definitionen ist jedoch F0 = 0, F1 = 1 die praktischere Konvention.
Fibonacci-Folge in der Programmierung
Die rekursive Definition lässt sich direkt in Code übersetzen. Das folgende Python-Beispiel verwendet die 0-basierte Indexierung:
def fib_rekursiv(n):
if n < 0:
raise ValueError("n muss mindestens 0 sein")
if n <= 1:
return n
return fib_rekursiv(n - 1) + fib_rekursiv(n - 2)
print(fib_rekursiv(6)) # 8Die Funktion funktioniert für kleine Werte, hat aber einen entscheidenden Nachteil: Sie berechnet dieselben Teilprobleme mehrfach. Bei fib_rekursiv(5) wird beispielsweise fib_rekursiv(3) aus mehreren Zweigen erneut aufgerufen. Die Anzahl der Aufrufe wächst dadurch sehr schnell; für größere Werte wird die naive Rekursion unpraktisch.
Eine iterative Variante speichert nur die beiden zuletzt benötigten Zahlen:
The Tool Desk
Outbyte Driver Updater FREEScan for outdated or missing drivers - takes under a minuteDriver Scan →Outbyte PC Repair FREEClear out junk files and repair common Windows errorsFree Scan →def fib_iterativ(n):
if n < 0:
raise ValueError("n muss mindestens 0 sein")
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_iterativ(6)) # 8Diese Version berechnet Fn in linearer Zeit, also mit O(n) Schleifendurchläufen, und benötigt konstanten zusätzlichen Speicher, also O(1). Für eine einzelne Fibonacci-Zahl ist sie meist die einfachste robuste Lösung.
Alternativ kann man die rekursive Struktur durch Memoisierung beschleunigen. Dabei wird jedes bereits berechnete Ergebnis gespeichert und bei einem späteren Aufruf wiederverwendet:
from functools import cache
@cache
def fib(n):
if n < 0:
raise ValueError("n muss mindestens 0 sein")
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(100))Memoisierung reduziert die Zahl der Berechnungen auf lineare Größenordnung, benötigt dafür aber Speicher für die Zwischenergebnisse.
Rank #3
Explizite Berechnung mit der Binet-Formel
Die Folge kann nicht nur rekursiv, sondern auch direkt berechnet werden. Für die 0-basierte Folge gilt die Binet-Formel:
Free tools Windows power users keep installed
One-click scans. No signup required.
Fn = (φn − ψn) / √5
Hierbei sind:
φ = (1 + √5) / 2 ≈ 1,6180339887ψ = (1 − √5) / 2
Obwohl die Formel irrationale Zahlen enthält, ergibt sich für ganzzahlige n exakt eine Fibonacci-Zahl. In gewöhnlichen Programmen ist die direkte Gleitkomma-Berechnung allerdings nicht immer die beste Wahl: Rundungsfehler können bei großen Indizes zu einem falschen ganzzahligen Ergebnis führen. Für exakte Berechnungen sind iterative Verfahren, Ganzzahlarithmetik oder spezialisierte Algorithmen wie schnelles Verdoppeln zuverlässiger.
Verbindung zum goldenen Schnitt
Der Quotient zweier aufeinanderfolgender Fibonacci-Zahlen nähert sich mit wachsendem Index dem goldenen Schnitt φ ≈ 1,6180339887:
| Quotient | Wert ungefähr |
|---|---|
F3 / F2 |
2 |
F6 / F5 |
1,6 |
F10 / F9 |
1,6176 |
für große n |
nahe 1,6180339887 |
Bei kleinen Indizes ist die Annäherung noch ungenau. Die Aussage bedeutet nicht, dass jeder Quotient der Folge bereits dem goldenen Schnitt entspricht.
Rank #4
Woher stammt die Folge?
Benannt ist die Folge nach Leonardo Fibonacci, auch Leonardo von Pisa genannt. Er machte sie in Europa durch sein 1202 erschienenes Werk Liber Abaci bekannt. Die mathematische Idee stammt jedoch nicht ursprünglich von ihm; frühere Belege gibt es insbesondere in der indischen Mathematik, außerdem finden sich verwandte Betrachtungen in der griechischen Mathematik.
Fibonacci beschrieb ein Modell zum Wachstum einer Kaninchenpopulation. In diesem Modell gelten stark vereinfachte Bedingungen, etwa regelmäßige Fortpflanzung und das Überleben aller Tiere. Es handelt sich daher um ein mathematisches Modell und nicht um eine realistische allgemeine Prognose für Tierpopulationen.
Fibonacci-Zahlen in Natur und Technik
Fibonacci-Zahlen tauchen in verschiedenen mathematischen Modellen und bei bestimmten natürlichen Strukturen auf. Beispiele werden häufig bei Blattstellungen, Blütenständen oder spiralförmigen Anordnungen genannt. Daraus folgt aber nicht, dass natürliche Wachstumsprozesse generell exakt der Fibonacci-Folge folgen.
In der Informatik begegnet die Folge unter anderem als Beispiel für:
Recommended Free Tools
- Rekursion und die damit verbundenen Laufzeitprobleme
- Memoisierung und dynamische Programmierung
- Folgen mit linearen Rekursionsgleichungen
- Algorithmen für große Indizes
- mathematische Induktion und Laufzeitanalyse
Verallgemeinerte Fibonacci-Folgen
Die klassische Folge ist nur ein Spezialfall einer größeren Familie. Ändert man die Anfangswerte oder die Koeffizienten der Rekursion, entsteht eine verallgemeinerte Fibonacci-Folge.
Best Value
Beispielsweise definiert
G0 = 2, G1 = 3 und Gn = Gn-1 + Gn-2
die Folge 2, 3, 5, 8, 13, 21, …. Ändert man zusätzlich die Koeffizienten, sind auch Regeln wie Hn = 2Hn-1 + Hn-2 möglich. Die klassische Fibonacci-Folge verwendet die Anfangswerte 0, 1 beziehungsweise 1, 1 und die Koeffizienten 1, 1.
FAQ
Was ist die Fibonacci-Folge einfach erklärt?
Eine Zahlenfolge, bei der jede Zahl aus der Addition der beiden vorherigen entsteht. In der 0-basierten Schreibweise beginnt sie mit 0, 1, 1, 2, 3, 5, 8, 13.
Beginnt die Fibonacci-Folge mit 0 oder mit 1?
Beides kommt vor. Die 0-basierte Schreibweise beginnt mit F₀ = 0 und F₁ = 1. Die 1-basierte Schreibweise beginnt mit F₁ = 1 und F₂ = 1. Es handelt sich um dieselbe Folge mit verschobenen Indizes.
Wie berechnet man F₆?
In der 0-basierten Schreibweise gilt F₆ = F₅ + F₄ = 5 + 3 = 8.
Hat Fibonacci die Folge erfunden?
Nein. Leonardo Fibonacci machte sie im mittelalterlichen Europa durch sein Werk Liber Abaci bekannt. Frühere mathematische Belege gibt es insbesondere in der indischen Mathematik.
Warum ist eine naive rekursive Fibonacci-Funktion langsam?
Sie berechnet dieselben Teilprobleme mehrfach. Bei größeren n wächst die Zahl der rekursiven Aufrufe dadurch sehr stark. Memoisierung oder eine iterative Berechnung vermeidet diese Wiederholungen.
Ist die Fibonacci-Folge überall in der Natur zu finden?
Nein. Fibonacci-Zahlen treten bei bestimmten natürlichen Strukturen und in mathematischen Modellen auf. Daraus folgt nicht, dass alle natürlichen Wachstumsprozesse exakt dieser Folge folgen.
Quick Recap
The Bottom Line
Das Wichtigste zur Fibonacci-Folge
- Die Folge entsteht aus der Summe der beiden vorherigen Glieder.
- Die verbreitete 0-basierte Definition lautet
F0 = 0,F1 = 1. - Eine 1-basierte Schreibweise mit
1, 1ist ebenfalls korrekt. - Iterative Berechnung oder Memoisierung ist für Programme deutlich geeigneter als naive Rekursion.
- Das Verhältnis aufeinanderfolgender Zahlen nähert sich dem goldenen Schnitt.
- Fibonacci popularisierte die Folge in Europa, erfand sie aber nicht.
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
