Ciąg Fibonacciego w C# — rekurencja i iteracja

Ciąg Fibonacciego to jeden z najsłynniejszych ciągów w matematyce — i jeden z najczęściej pojawiających się tematów na rozmowach rekrutacyjnych z programowania. Każdy wyraz, oprócz dwóch pierwszych, jest sumą dwóch poprzednich wyrazów. Zaczyna się od 0, 1, a każdy kolejny element otrzymujemy, dodając do siebie dwa poprzednie:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …

Ten artykuł skupia się na definicji, matematycznym pochodzeniu i podstawowej implementacji ciągu. Jeśli przygotowujesz się do rozmowy rekrutacyjnej i szukasz analizy złożoności obliczeniowej, memoizacji i pułapek z przepełnieniem typów, zobacz dedykowany artykuł: Ciąg Fibonacciego — zadanie rekrutacyjne.

Definicja matematyczna

Formalnie ciąg Fibonacciego definiuje się rekurencyjnie:

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) dla n > 1

To klasyczny przykład relacji rekurencyjnej — definicji, w której kolejny element zależy od poprzednich elementów tego samego ciągu. Ta sama zasada (choć z inną formułą) stoi za wieloma innymi ciągami matematycznymi używanymi w informatyce, np. w analizie algorytmów typu dziel-i-zwyciężaj.

Gdzie występuje w praktyce

Ciąg Fibonacciego to nie tylko ćwiczenie akademickie — pojawia się zaskakująco często:

• Złoty podział — stosunek kolejnych wyrazów ciągu (np. F(n+1)/F(n)) zbliża się w nieskończoności do liczby φ ≈ 1,618, znanej jako złota liczba, wykorzystywanej w sztuce, architekturze i projektowaniu UI.
• Przyroda — liczba płatków wielu kwiatów, spirale muszli ślimaków czy układ nasion w słoneczniku często odpowiadają kolejnym liczbom Fibonacciego.
• Struktury danych — kopce Fibonacciego (Fibonacci heap) używają tej sekwencji do analizy złożoności amortyzowanej operacji.
• Rozmowy rekrutacyjne — jako test znajomości rekurencji, złożoności obliczeniowej i optymalizacji (patrz link na górze artykułu).

Rozwiązanie rekurencyjne

Najbardziej naturalne tłumaczenie definicji matematycznej wprost na kod:

private static int Fib(int n)
{
    if (n <= 1)
    {
        return n;
    }

    return Fib(n - 1) + Fib(n - 2);
}

Ten kod jest czytelny i wiernie odzwierciedla definicję matematyczną — Fib(n) wywołuje samo siebie dla n-1 i n-2, dokładnie jak w formule. Można go też skrócić do jednej linijki za pomocą operatora warunkowego:

private static int Fib(int n)
    => n <= 1 ? n : Fib(n - 1) + Fib(n - 2);

Problem: dla większych n ta implementacja liczy te same podwyrazy wielokrotnie — Fib(5) wywołuje Fib(3) dwukrotnie, a Fib(2) trzykrotnie. Liczba wywołań rośnie wykładniczo. Pełną analizę złożoności (O(2ⁿ)) i sposoby jej naprawy (iteracja, memoizacja) znajdziesz w artykule o zadaniu rekrutacyjnym.

Rozwiązanie iteracyjne

Zamiast wywoływać funkcję wielokrotnie, wystarczy pamiętać tylko dwie ostatnie wartości i przesuwać je w pętli:

private static int Fib(int n)
{
    int a = 0, b = 1;

    for (int i = 0; i < n; i++)
    {
        (a, b) = (b, a + b);
    }

    return a;
}

W każdej iteracji b staje się nowym wyrazem (sumą poprzednich a i b), a a przejmuje starą wartość b. Krotka (a, b) = (b, a + b) (dostępna od C# 7) wykonuje to przypisanie równolegle, bez potrzeby zmiennej tymczasowej. Ta wersja liczy każdy wyraz dokładnie raz, więc jest liniowa względem n — nieporównywalnie szybsza od naiwnej rekurencji dla większych wartości.

Wzór Bineta — bez pętli i rekurencji

Istnieje też zamknięty wzór matematyczny (wzór Bineta), który pozwala obliczyć n-ty wyraz bezpośrednio, bez iterowania po wszystkich poprzednich — wykorzystuje właśnie złotą liczbę φ:

private static long FibBinet(int n)
{
    double phi = (1 + Math.Sqrt(5)) / 2;
    double psi = (1 - Math.Sqrt(5)) / 2;

    return (long)Math.Round((Math.Pow(phi, n) - Math.Pow(psi, n)) / Math.Sqrt(5));
}

To rozwiązanie ma teoretyczną złożoność O(1), ale w praktyce operuje na liczbach zmiennoprzecinkowych double, więc dla dużych n błędy zaokrągleń psują dokładność wyniku — dla wartości powyżej ok. n = 70 wynik przestaje być wiarygodny. To ciekawostka matematyczna, a nie rekomendowane rozwiązanie produkcyjne — do tego lepiej nadaje się iteracja pokazana wyżej.

Sprawdzamy działanie

static void Main(string[] args)
{
    int number = 10;
    Console.WriteLine($"{number}. wyraz ciągu Fibonacciego to: {Fib(number)}");
    // 10. wyraz ciągu Fibonacciego to: 55
}

FAQ

Czy ciąg zaczyna się od 0 czy od 1?
Zależy od konwencji — najczęściej przyjmuje się F(0) = 0, F(1) = 1 (jak w tym artykule), choć niektóre źródła pomijają zerowy wyraz i zaczynają od dwóch jedynek. Warto to doprecyzować na rozmowie rekrutacyjnej, zamiast zakładać jedną wersję.

Która implementacja jest najlepsza do użycia w kodzie produkcyjnym?
Iteracyjna — jest szybka (O(n)), zużywa stałą ilość pamięci (O(1)) i nie ryzykuje przepełnienia stosu wywołań dla dużych n, w przeciwieństwie do rekurencji.

Dlaczego naiwna rekurencja jest tak wolna?
Bo wielokrotnie przelicza te same podproblemy zamiast zapamiętać już policzone wartości. Szczegółowy rozkład złożoności O(2ⁿ) i sposoby naprawy (memoizacja) znajdziesz w artykule o zadaniu rekrutacyjnym.

Powiązane: zobacz algorytmy krok po kroku i klasyfikację algorytmów.