Fibonacci Zahlen - funktional

Hintergrundwissen

Bei den Fibonacci Zahlen handelt es sich um eine unendliche Zahlenreihe. Ursprünglich wurde die Fibonacci-Folge zur Beschreibung des Wachstums einer Kaninchenpopulation verwendet. Diese erfolgt progressiv. Am Anfang gibt es ein Kaninchenpaar, dieses wird im zweiten Monat zeugungsfähig und zeugt jeden Monat ein weiteres Paar Kaninchen. Keins der Kaninchen stirbt. Das heißt die die Summe der benachbarten Zahlen ergibt die nächste Zahl ( 0,1,1,2,3,5,8,...).

${\displaystyle f_{0}=0}$

${\displaystyle f_{1}=1}$

${\displaystyle f_{2}=1=f_{0}+f_{1}}$

${\displaystyle f_{3}=2=f_{1}+f_{2}}$

${\displaystyle f_{4}=3=f_{2}+f_{3}}$

...

${\displaystyle fib(x):=\left\{{\begin{array}{ll}x-te~Fibonacci-Zahl&fals~x\geq 0\\\bot &sonst\end{array}}\right.}$

Programm

fib(x)  :=  if (x==0) then 0 
        else if (x==1)  then  1
                else  fib(x-1) + fib(x-2)

Literatur

Da die Vorlesungsinhalte auf dem Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.2.6 zu finden.