Silnia — Zadanie rekrutacyjne #3

Czego szuka rekruter: rekurencja vs iteracja, rozumienie ograniczeń typów, obsługa edge cases
Poziom: Junior / Mid

Zadanie

Napisz funkcję obliczającą silnię liczby całkowitej n (n!). Silnia zdefiniowana jest jako iloczyn wszystkich liczb całkowitych od 1 do n. Przyjmujemy że 0! = 1.

Czego szuka rekruter

Silnia jest klasycznym testem rekurencji, ale rekruter oczekuje czegoś więcej:

• Znajomość obu podejść — rekurencja i iteracja — i umiejętność wyjaśnienia różnicy
• Świadomość ograniczeń typów — int przepełnia się już przy 13!, long przy 21!
• Obsługa nieprawidłowych wejść — co dla ujemnego n?
• Świadomość przepełnienia stosu — głęboka rekurencja rzuca StackOverflowException

Edge cases do przemyślenia

Rozwiązanie iteracyjne — preferowane w produkcji

static long Factorial(int n)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(nameof(n), "Silnia nie jest zdefiniowana dla liczb ujemnych.");
    
    if (n == 0 || n == 1)
        return 1;
    
    long result = 1;
    for (int i = 2; i <= n; i++)
    {
        result *= i;
    }
    return result;
}

Dlaczego iteracyjne? Nie tworzy klatek na stosie — dla n = 100 000 wersja rekurencyjna rzuci StackOverflowException, iteracyjna policzy (choć overflow w long nastąpi dużo wcześniej).

Rozwiązanie rekurencyjne — klasyczne, ale z zastrzeżeniami

static long FactorialRecursive(int n)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(nameof(n));
    
    return n == 0 ? 1 : n * FactorialRecursive(n - 1);
}

Rekurencja tworzy n klatek na stosie. Dla małych n jest OK — elegancka i odzwierciedla definicję matematyczną. W C# brak optymalizacji TCO (tail-call optimization), więc FactorialRecursive(100_000) wysypie program.

Wersja z BigInteger — dla dużych n

using System.Numerics;

static BigInteger FactorialBig(int n)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(nameof(n));
    
    BigInteger result = 1;
    for (int i = 2; i <= n; i++)
        result *= i;
    return result;
}

// FactorialBig(100) = 93326215443944152681699238856...  (158 cyfr)

Testy jednostkowe

[Theory]
[InlineData(0, 1)]
[InlineData(1, 1)]
[InlineData(5, 120)]
[InlineData(10, 3628800)]
[InlineData(12, 479001600)]
public void Factorial_ReturnsCorrectValue(int n, long expected)
{
    Assert.Equal(expected, Factorial(n));
}

[Fact]
public void Factorial_NegativeInput_ThrowsArgumentOutOfRangeException()
{
    Assert.Throws<ArgumentOutOfRangeException>(() => Factorial(-1));
}

Co powiedzieć na rozmowie

“Wolę wersję iteracyjną — nie ryzykuje StackOverflow i jest wydajniejsza pamięciowo. Rekurencyjna jest elegantszy matematycznie i pokazuje jak definicja przekłada się na kod, ale w .NET nie mamy TCO więc nie skaluje. Jeśli potrzebujemy dużych wartości — BigInteger.”

Podsumowanie

Silnia testuje znajomość rekurencji, ale dobre odpowiedzi idą dalej: świadomość ograniczeń long, brak TCO w C# i istnienie BigInteger jako alternatywy dla dużych wyników.