Rekurencja i matrioszki

function policzMatrioszki(matrioszka) {
  // Warunek bazowy: najmniejsza laleczka
  if (matrioszka.wSrodku === null) {
    return 1;
  }
  // Krok rekurencyjny: 1 (ta) + to, co jest w środku
  return 1 + policzMatrioszki(matrioszka.wSrodku);
}

Definicja #

Funkcja rekurencyjna to funkcja wywołująca samą siebie (bezpośrednio lub przez pośrednika - rekurencja wzajemna). Każde wywołanie tworzy nową ramkę (stack frame) z własnymi parametrami i zmiennymi lokalnymi.

Kontrakt - dwa elementy obowiązkowe #

int Factorial(int n)
{
    if (n <= 1) return 1;          // (1) base case
    return n * Factorial(n - 1);   // (2) recursive step z mniejszym inputem
}

• Base case - warunek zakończenia. Bez niego stack overflow.
• Recursive step - redukcja problemu w kierunku base case. Jeśli argument nie maleje, utkniesz.

Call stack - co siedzi pod spodem #

.NET alokuje wątkom domyślny stos (~1 MB na 64-bit). Każde wywołanie metody to ramka:

• Adres powrotu.
• Zapisane rejestry.
• Parametry i zmienne lokalne.

Dla Factorial(1000) potrzebujesz 1000 ramek. Dla Factorial(1_000_000) - StackOverflowException, nie do złapania (proces pada).

Sprawdzenie na szybko:

try { Factorial(100_000); }
catch (StackOverflowException) { /* nie tu, proces umrze */ }

TCO - którego C# (prawie) nie ma #

Tail call optimization pozwala skompilować wywołanie rekurencyjne w ostatniej pozycji jako skok (zamiast push ramki). Wynik: O(1) stack dla rekurencji ogonowej.

JIT w .NET potrafi to robić (szczególnie w Release/x64), ale nie jest gwarantowane - spec języka nie wymaga. Dla stabilnego O(1) stosu przepisz na iterację:

// Rekurencyjnie - zależne od kaprysów JIT-a
int Sum(int n, int acc = 0) =>
    n == 0 ? acc : Sum(n - 1, acc + n);

// Iteracyjnie - zawsze O(1) stack
int SumIter(int n)
{
    int acc = 0;
    while (n > 0) { acc += n; n--; }
    return acc;
}

F# i inne języki funkcyjne gwarantują TCO - używaj rekurencji swobodnie. W C# - ostrożnie dla głębokich zejść.

Kiedy rekurencja jest naturalna #

Struktury rekurencyjne - drzewa, grafy, JSON, XML, AST, system plików. Iteracyjny kod dla drzewa wymaga ręcznego Stack<T>:

// title: TreeWalk.cs
record TreeNode(int Value, List<TreeNode> Children);

// Rekurencyjnie - czytelne
int Sum(TreeNode node)
{
    int total = node.Value;
    foreach (var child in node.Children)
        total += Sum(child);
    return total;
}

// Iteracyjnie z explicit stack
int SumIter(TreeNode root)
{
    var stack = new Stack<TreeNode>();
    stack.Push(root);
    int total = 0;
    while (stack.Count > 0)
    {
        var node = stack.Pop();
        total += node.Value;
        foreach (var child in node.Children)
            stack.Push(child);
    }
    return total;
}

Drugi wariant wygrywa tylko gdy drzewo jest wyjątkowo głębokie (ryzyko SOE).

Memoizacja - rekurencja z tablicą wyników #

Naiwny Fibonacci jest O(2^n):

long Fib(int n) => n < 2 ? n : Fib(n - 1) + Fib(n - 2);
// Fib(40) już wolne, Fib(50) - minuty

Problem: te same wartości liczone wielokrotnie. Memoizacja cache’uje wynik dla danego argumentu:

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

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

Złożoność spada do O(n) - każdy n liczony raz.

Divide and conquer - rekurencja z redukcją 2:1 #

Merge sort, quicksort, binary search - wszystkie dzielą problem na dwie połowy i rozwiązują rekurencyjnie. Złożoność opisana Master Theorem:

T(n) = 2 * T(n/2) + O(n) → O(n log n) (merge sort).

Szczegóły w osobnym wpisie o merge sort.

Pułapki #

• Shared mutable state - rekurencyjne metody modyfikujące pole klasy trudne do debugowania, szczególnie wielowątkowo.
• Allocations - rekurencja na listach przez .Skip(1).ToList() tworzy O(n) kopii. Używaj indeksu / ReadOnlySpan<T>.
• Captured closures - lambdy rekurencyjne (przez Func<> zmienną) alokują delegate + closure.
• Deserializacja JSON / XML z referencjami cyklicznymi - bez MaxDepth lub detekcji cykli wali SOE na sprytnie sfabrykowanym inpucie. Bezpieczeństwo.

Kiedy wybrać co #

Sytuacja	Wybierz
Płaska iteracja po kolekcji	pętla / LINQ
Drzewo / graf o nieznanej głębokości	rekurencja (jeśli głębokość < kilku tysięcy)
Gwarantowana głęboka struktura (niskopoziomowy parser, deserializacja)	iteracja z explicit stack
Problem “dzielony na dwa”	rekurencja
Hot path, zero alokacji	iteracja

Skrótowo #

Rekurencja to kompaktowy zapis dla problemów samo-podobnych. Mechanicznie: stos wywołań + warunek bazowy + krok redukujący. W C# uważaj na brak gwarantowanego TCO, memoizuj gdy widzisz wykładniczy blowup, dla naprawdę głębokich struktur używaj explicit stack.