Przypomnienie wiadomości

Nim dowiemy się, jak zdefiniować ciąg Fibonacciego, przypomnijmy sobie, na czym polega rekurencja. Mamy z nią do czynienia, gdy funkcja wywołuje samą siebie w celu rozwiązania konkretnego problemu.

Ciąg Fibonacciego jest ciągiem liczb naturalnych. Jego pierwszy wyraz ma wartość 0, drugi 1, a każdy kolejny jest sumą dwóch poprzednich wyrazów ciągu.

Definicja ciągu Fibonacciego ma następującą postać:

$F_n=\{\begin{array}{ll}0& \text{dla }n=0\\ 1& \text{dla }n=1\\ F_{n-1}+F_{n-2}& \text{dla }n>1\end{array}$

Przedstawione wywołania funkcji rekurencyjnej można zobrazować przy użyciu drzewa wywołań rekurencyjnych:

R1aysrpZyBaBW

Drzewo wywołań rekurencyjnych.
1: F5, 2: strzałka w lewo: F4. 3: Strzałka w prawo: F2, 4: strzałka w prawo: F0, 5: strzałka w lewo: F1, 2: strzałka w lewo F3, 3: strzałka w prawo F1, 3: strzałka w lewo: F2, 4: strzałka w lewo: f1, 4: strzałka w prawo: F0.
2: strzałka w prawo: F3, 3: strzałka wprawo: F1, 3: strzałka w lewo: F2, 4: strzałka w lewo: F1, 4: strzałka w prawo F0.

Jakie są wartości kilkunastu początkowych wyrazów ciągu Fibonacciego? Są nimi liczby: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

Postać rekurencyjna

Zapisany niżej algorytm opiera się na przedstawionej wcześniej definicji wyrazów ciągu Fibonacciego. Odpowiedni pseudokod wygląda następująco:

funkcja fibonacci(n)
	jeżeli n == 0 wykonaj:
		zwróć 0
	w przeciwnym razie jeżeli n == 1 wykonaj:
		zwróć 1
	w przeciwnym razie wykonaj:
		zwróć Fibonacci(n - 1) + Fibonacci(n - 2)

Rekurencyjny algorytm przedstawiony powyżej jest prosty. Niestety, program napisany z jego wykorzystaniem okazuje się mało wydajny: działa bardzo wolno i nadaje się jedynie do obliczania kilku pierwszych wyrazów ciągu. Wynika to z faktu, że w celu wyznaczenia wybranego elementu ciągu wielokrotnie są obliczane te same, poprzedzające go wartości. W rezultacie złożoność czasowa algorytmu jest wykładnicza. Tym samym czas działania programu będzie znacznie dłuższy dla coraz dalszych wyrazów. Istnieje ponadto ryzyko wystąpienia błędu przepełnienia pamięciprzepełnienie pamięciprzepełnienia pamięci z powodu zbyt dużej liczby wywołań funkcji rekurencyjnej. W związku z tym należy stosować wersję iteracyjną algorytmu, pozwalającego wyliczyć kolejne wyrazy ciągu Fibonacciego. Przedstawimy go w kolejnej sekcji materiału.

Co to jest złota liczba?

Elementy ciągu Fibonacciego mają ciekawą cechę. Ilorazy dwóch kolejnych wyrazów są w przybliżeniu równe 1,618. Jest to tym bardziej widoczne, im większe liczby dzielimy przez siebie: wraz ze zbliżaniem się do nieskończoności uzyskujemy lepsze przybliżenie wartości 1,618. Liczbę tę nazywamy „złotą proporcją” lub „złotą liczbą”.

Liczby Fibonacciego wokół nas

Liczba płatków kwiatu jest przeważnie liczbą Fibonacciego. Podobnie jest z ulistnieniem i właśnie dlatego tak trudno jest znaleźć czterolistną koniczynę. W normalnych warunkach, gdy nie zachodzi żadna hodowla, kwiaty mają: 1, 2, 3, 5, 8, 13, 21, a niektóre gatunki nawet po 34 płatki lub więcej, np. stokrotka.

Liczby Fibonacciego odnajdziemy także, przyglądając się niektórym proporcjom ludzkiego ciała. W proporcjach ciała harmonijnie rozwiniętego człowieka znajdziemy złotą proporcję. Co prawda, nie zawsze są one idealnie i dokładnie zachowane, ale są na pewno bardzo zbliżone.

Złotą liczbę otrzymasz m.in. z następujących stosunków:

• odległość od pępka do czubka głowy do odległości od ramion do czubka głowy;

• odległość od ramion do czubka głowy do odległości od brody do czubka głowy;

• wysokość twarzy do jej szerokości;

• odległość od kolana do pępka do odległości od kolana do stopy;

• odległość od koniuszków palców do łokcia do odległości od nadgarstka do łokcia;

• dzieląc wzrost człowieka przez odległość od stóp do pępka.

Ciąg Fibonacciego można również odnaleźć w muzyce. Wiele utworów, zarówno współczesnych, jak i tych starszych, jest opartych na kanonie Pachelbela. Nuty tego utworu są zapisane na podstawie ciągu Fibonacciego.

Przedstawiliśmy tylko kilka spośród wielu przypadków, w których da się zauważyć liczby Fibonacciego w otaczającym nas świecie. Napotkamy je też w literaturze, sztuce, ekonomii, architekturze czy religii.

Słownik