Czym są liczby Fibonacciego?
Liczby Fibonacciego tworzą ciąg liczbowy, w którym każdy kolejny wyraz jest sumą dwóch poprzednich. Najczęściej przyjmuje się:
F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2)
Początek ciągu wygląda tak:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Dlaczego Fibonacci kojarzy się z rekurencją?
Definicja ciągu Fibonacciego sama odwołuje się do wcześniejszych wyrazów tego samego ciągu. Dlatego bardzo naturalnie zapisuje się ją jako funkcję rekurencyjną.
Przykład w Pythonie:
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
Funkcja fib wywołuje samą siebie, więc jest przykładem rekurencji.
Wada prostego rozwiązania rekurencyjnego
Prosta wersja rekurencyjna jest czytelna, ale ma słabą wydajność. Wiele wartości jest obliczanych wielokrotnie, np. fib(5) ponownie liczy fib(3), fib(2) itd.
Dlatego w praktyce często stosuje się:
- wersję iteracyjną,
- zapamiętywanie wyników, czyli memoizację,
- programowanie dynamiczne.
Znaczenie egzaminacyjne
Jeżeli w pytaniu pojawia się wybór między sortowaniem bąbelkowym, wyszukiwaniem liniowym, sortowaniem przez wstawianie i liczbami Fibonacciego, to z rekurencją najczęściej łączy się właśnie obliczanie liczb Fibonacciego.