Rekurencyjne obliczanie ciągu Fibonacciego z omówieniem problemu nakładania się podproblemów.
Wersja rekurencyjna ciągu Fibonacciego to bezpośrednia implementacja matematycznej definicji: funkcja wywołuje samą siebie dla n - 1 i n - 2, a wyniki sumuje. Warunki bazowe: F(1) = F(2) = 1.
Problem wydajności: algorytm ma wykładniczą złożoność O(2ⁿ), ponieważ wielokrotnie przelicza te same wartości. Na przykład dla F(5) funkcja oblicza F(3) dwa razy, F(2) trzy razy.
Złożoność pamięciowa O(n) wynika z głębokości stosu wywołań rekurencyjnych – dla F(n) stos osiąga głębokość n.
Po co uczyć się wersji rekurencyjnej? Mimo że jest bardzo nieefektywna, jest świetnym przykładem rekurencji i pokazuje, jak naturalny zapis matematyczny może być nieoptymalny w implementacji. Z tego powodu często pojawia się na maturze.
Optymalizacja: używając memoizacji (zapamiętywania wyników) można zredukować złożoność do O(n) zachowując rekurencyjny styl.
funkcja fibonacci_rek(n): // warunki bazowe rekurencji jeżeli n ≤ 2: zwróć 1 // wywołanie rekurencyjne zgodnie z definicją zwróć fibonacci_rek(n - 1) + fibonacci_rek(n - 2)
def fibonacci_rek(n):
if n <= 2:
return 1
return fibonacci_rek(n - 1) + fibonacci_rek(n - 2)
# Przykład użycia
print(fibonacci_rek(10))
# Wynik: 55
# Uwaga - dla n > 35 algorytm będzie bardzo wolny
# fibonacci_rek(50) liczyłoby się minutyO(2ⁿ)O(n)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: