Ciąg Fibonacciego — Zadanie rekrutacyjne #4

Czego szuka rekruter: rekurencja z memoizacją, iteracja, złożoność obliczeniowa
Poziom: Junior / Mid

Zadanie

Wypisz pierwsze n liczb ciągu Fibonacciego. Ciąg zaczyna się: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34…
Każda liczba to suma dwóch poprzednich: F(n) = F(n-1) + F(n-2), gdzie F(0) = 0, F(1) = 1.

Czego szuka rekruter

Fibonacci to klasyczny test wiedzy o złożoności obliczeniowej. Rekruter świadomie czeka, czy kandydat:

• Napisze naiwną rekurencję O(2ⁿ) i zatrzyma się na niej — zły znak
• Sam zauważy problem wydajnościowy i zaproponuje poprawkę — dobry znak
• Zna memoizację lub wersję iteracyjną — bardzo dobry znak

Naiwna rekurencja dla n = 50 liczy Fibonacci(50) ~ 2^50 razy. Przy n = 40 trwa kilkadziesiąt sekund. Przy n = 100 procesor skapituluje.

❌ Naiwna rekurencja — O(2ⁿ)

// NIE rób tego dla dużych n
static long FibNaive(int n)
{
    if (n <= 1) return n;
    return FibNaive(n - 1) + FibNaive(n - 2);
}

Problem: FibNaive(5) wywołuje FibNaive(3) dwa razy, FibNaive(2) trzy razy itd. Ogromna liczba powtarzających się obliczeń.

✅ Iteracja — O(n) czas, O(1) pamięć

static IEnumerable<long> Fibonacci(int count)
{
    if (count <= 0) yield break;
    
    long a = 0, b = 1;
    for (int i = 0; i < count; i++)
    {
        yield return a;
        (a, b) = (b, a + b);
    }
}

// Użycie:
foreach (var n in Fibonacci(15))
    Console.WriteLine(n);
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377

yield return sprawia, że obliczamy kolejne wartości leniwie — nie trzymamy całego ciągu w pamięci.

✅ Memoizacja — O(n) czas, O(n) pamięć

static readonly Dictionary<int, long> _cache = new() { [0] = 0, [1] = 1 };

static long FibMemo(int n)
{
    if (_cache.TryGetValue(n, out long cached))
        return cached;
    
    long result = FibMemo(n - 1) + FibMemo(n - 2);
    _cache[n] = result;
    return result;
}

Oblicza każdą wartość dokładnie raz i zapisuje. Zachowuje czytelność rekurencyjnej definicji, ale jest bezpieczna dla dużych n.

Ograniczenia typów

// long: maksymalnie F(92) = 7 540 113 804 746 346 429
// F(93) przekracza long.MaxValue → overflow
Console.WriteLine(FibMemo(92));  // OK
Console.WriteLine(FibMemo(93));  // OverflowException (checked) lub błędny wynik (unchecked)

// Dla nieograniczonych wartości:
using System.Numerics;
static BigInteger FibBig(int n)
{
    BigInteger a = 0, b = 1;
    for (int i = 0; i < n; i++)
        (a, b) = (b, a + b);
    return a;
}

Testy jednostkowe

[Theory]
[InlineData(0, new long[] { })]
[InlineData(1, new long[] { 0 })]
[InlineData(5, new long[] { 0, 1, 1, 2, 3 })]
[InlineData(8, new long[] { 0, 1, 1, 2, 3, 5, 8, 13 })]
public void Fibonacci_ReturnsCorrectSequence(int count, long[] expected)
{
    Assert.Equal(expected, Fibonacci(count).ToArray());
}

Co powiedzieć na rozmowie

“Naiwna rekurencja ma złożoność O(2ⁿ) bo wielokrotnie przelicza te same podzadania. Wersja iteracyjna jest O(n) i O(1) pamięci — najlepsza dla wypisania ciągu. Memoizacja zachowuje czytelność rekurencji ale wymaga O(n) pamięci. Dla bardzo dużych n musimy przejść na BigInteger bo long overflow’uje na F(93).”

Podsumowanie