Fibonacci-Zahl
Berechnet die n-te Fibonacci-Zahl. Definition: F(0) = 0, F(1) = 1, F(n) = F(n − 1) + F(n − 2).
Fibonacci-Zahl berechnen
Berechnet die n-te Fibonacci-Zahl. Definition: F(0) = 0, F(1) = 1, F(n) = F(n − 1) + F(n − 2).
Was ist die Fibonacci-Folge?
Die Fibonacci-Folge ist eine berühmte Zahlenfolge, bei der jedes Glied die Summe der beiden vorherigen ist. Sie startet mit 0 und 1:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …
Die Folge taucht in unerwarteten Zusammenhängen auf — bei Pflanzen-Spiralen, in der Kunst, in Algorithmen und in der Finanzanalyse. Das Verhältnis benachbarter Glieder konvergiert gegen den Goldenen Schnitt φ ≈ 1,618.
Die Formel
Die Fibonacci-Folge ist rekursiv definiert:
F(0) = 0
F(1) = 1
F(n) = F(n − 1) + F(n − 2) für n ≥ 2In der Praxis berechnet man die Folge iterativ — die naive Rekursion ist exponentiell langsam, weil sie dieselben Werte ständig neu berechnet.
Die Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| n | Index | — | Position in der Fibonacci-Folge, n ≥ 0. |
| Fn | Fibonacci-Zahl | — | Wert der n-ten Fibonacci-Zahl. |
Ab n ≈ 78 verlässt das Ergebnis den exakt darstellbaren Integer-Bereich gängiger 64-Bit-Floats — sehr große Werte sind also Approximationen.
Minimal-Beispiel
F(7) iterativ:
F(0) = 0
F(1) = 1
F(2) = 0 + 1 = 1
F(3) = 1 + 1 = 2
F(4) = 1 + 2 = 3
F(5) = 2 + 3 = 5
F(6) = 3 + 5 = 8
F(7) = 5 + 8 = 13Praxis-Beispiele
Beispiel 1 — Erste 15 Glieder
n F(n)
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377Beispiel 2 — F(20)
F(15) = 610
F(16) = 987
F(17) = 1.597
F(18) = 2.584
F(19) = 4.181
F(20) = 6.765Beispiel 3 — Goldener Schnitt
Das Verhältnis F(n) / F(n − 1) konvergiert gegen φ ≈ 1,6180339887:
F(10) / F(9) = 55 / 34 ≈ 1,617647
F(15) / F(14) = 610 / 377 ≈ 1,618037
F(20) / F(19) = 6765 / 4181 ≈ 1,618034Beispiel 4 — Schnelles Wachstum
F(30) = 832.040
F(50) = 12.586.269.025
F(78) ≈ 8,944 · 10^15 (Grenze des präzisen Integers)