Die ihm zu Ehren so genannte Folge der Fibonacci-Zahlen tritt in der Mathematik, der Informatik, der Architektur und auch in vielen anderen Bereichen immer wieder unvermutet wie ein Springteufel auf (einmal habe ich mit ihrer Hilfe sogar in der Spielbank gewonnen), und es lohnt sich, sie genauer zu untersuchen; an ihrem Beispiel lassen sich auch viele Programmiertechniken gut studieren.

Das (etwas unrealistische) Modell unserer Kaninchen-Population betrachtet Paare von ewig lebenden Kaninchen, die nach ihrem ersten Lebensmonat jeden Monat ein weiteres Paar produzieren. Innerhalb eines beliebigen Monats sind also die Kaninchen noch da, die im Monat vorher vorhanden waren; dazu kommen die Nachkommen derjenigen, die damals schon einen Monat alt waren, also einen Monat früher schon da waren. Wir fangen mit einem neugeborenen Paar im Monat 1 an; wenn wir mit F(n) die Anzahl der Paare im Monat n bezeichnen, so gilt also

(1) F(n) = F(n-1) + F(n-2) für n > 2
(2) F(1) = F(2) = 1

Aus der rekursiven Definition ergibt sich unmittelbar eine Funktionsprozedur:

PROCEDURE Fib(n: CARDINAL): CARDINAL;
BEGIN IF n <= 2 THEN RETURN 1
      ELSE RETURN Fib(n-1) + Fib(n-2)
      END;
END Fib;