Silnia w C# — rekurencja czy iteracja

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.

Dlaczego akumulator nie pomaga w C#

W językach z optymalizacją wywołań ogonowych (np. F#) przepisanie funkcji tak, by wywołanie rekurencyjne było ostatnią operacją (tail call), pozwala kompilatorowi zamienić rekurencję na pętlę pod maską — bez rosnącego stosu:

static long FactorialTailStyle(int n, long accumulator = 1)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(nameof(n));

    if (n == 0 || n == 1)
        return accumulator;

    // Wywołanie rekurencyjne jest tu ostatnią operacją — "tail call"
    return FactorialTailStyle(n - 1, n * accumulator);
}

Ta wersja wygląda na tail-recursive, ale w C# i tak utworzy n klatek na stosie — CLR (w przeciwieństwie do np. Tail calls w niektórych implementacjach funkcyjnych) nie gwarantuje eliminacji tail call dla zwykłych metod C#. Innymi słowy: w C# nie ma skrótu, który zamieni rekurencję w pętlę za Ciebie — jeśli chcesz uniknąć rosnącego stosu, musisz napisać jawną pętlę, jak w wersji iteracyjnej wyżej.

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, nawet w wersji z akumulatorem. Jeśli potrzebujemy dużych wartości — BigInteger.”

FAQ

Czy silnia z akumulatorem jest szybsza niż zwykła rekurencja?
W C# — nie, obie tworzą tyle samo klatek na stosie, bo CLR nie eliminuje tail calls dla metod C#. Wersja z akumulatorem jest wartościowa dydaktycznie (pokazuje wzorzec tail-recursive), ale realnej korzyści wydajnościowej nie daje — po nią sięgaj świadomie w językach, które faktycznie optymalizują tail calls.

Od jakiego n zaczyna się realne ryzyko StackOverflowException?
Zależy od dostępnego rozmiaru stosu wątku (domyślnie ok. 1 MB w .NET), ale rzędu dziesiątek–setek tysięcy wywołań, czyli znacznie wcześniej niż typowe dane wejściowe do liczenia silni — w praktyce i tak wcześniej napotkasz overflow long przy n = 21.

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.

Powiązane: silnia to klasyka rekurencji — zobacz pokrewne zadania Ciąg Fibonacciego i Liczba pierwsza oraz teorię pętli w C#.