Masz metodę, która powinna przejść do następnego folderu, a zamiast tego wciąż wywołuje samą siebie? Rekurencja zwykle pozwala rozwiązać problem przez rozwiązanie jego mniejszej wersji, ale działa poprawnie tylko wtedy, gdy każde wywołanie zbliża się do końca.
Rekurencja rozwiązuje mniejszy problem, aż dotrze do końca
- Wywołanie własnej metody tworzy kolejny krok obliczeń.
- Warunek bazowy zatrzymuje dalsze wywołania.
- Każdy krok musi upraszczać problem, inaczej metoda może wywoływać się bez końca.
- Głęboka rekurencja w C# grozi przepełnieniem stosu; dla nieznanej głębokości bezpieczniejsza bywa pętla ze stosem.

Metoda wraca do siebie, ale musi mieć dokąd dojść
Wyobraź sobie przeglądanie katalogów projektu: otwierasz folder, sprawdzasz jego zawartość, a gdy trafiasz na podfolder, wykonujesz tę samą czynność jeszcze raz. To właśnie intuicja rekurencji: ta sama metoda rozwiązuje problem w coraz mniejszej skali.
W C# metoda rekurencyjna wywołuje samą siebie. Potrzebuje jednak warunku bazowego, czyli sytuacji, w której zna wynik i kończy pracę bez kolejnego wywołania. Bez niego każde „jeszcze jeden folder” może prowadzić do następnego, a program nie wróci do początku.
Przeczytaj również: Klasa statyczna w C# - kiedy warto jej użyć?
Silnia pokazuje oba elementy
Silnię liczby nieujemnej można opisać jako iloczyn tej liczby i silni poprzedniej. Dla zera wynik jest ustalony, więc ten przypadek zamyka obliczenie:
static int Silnia(int n)
{
if (n < 0)
throw new ArgumentOutOfRangeException(nameof(n));
if (n == 0)
return 1;
return n * Silnia(n - 1);
}
Wywołanie Silnia(4) schodzi kolejno do Silnia(0), a potem wraca z wynikami: 1, 1, 2, 6 i 24. Najpierw powstaje łańcuch oczekujących wywołań, potem wyniki wracają w odwrotnej kolejności. W tym przykładzie widać też, dlaczego warunek bazowy i zmniejszanie argumentu muszą do siebie pasować.
Przy przejściu drzewa głębokość jest ważniejsza niż liczba elementów
Załóżmy, że narzędzie analizuje drzewo katalogów z 50 plikami, a najdłuższa ścieżka ma tylko cztery poziomy podfolderów. Rekurencyjne przejście wykona pracę dla plików i katalogów, ale liczba kolejnych wywołań naraz zależy głównie od najgłębszej ścieżki, nie od samej liczby plików.
To rozróżnienie łatwo przeoczyć. Drzewo z tysiącami plików ułożonych płytko może wymagać niewielkiej głębokości rekurencji, podczas gdy łańcuch zagnieżdżonych katalogów może ją zwiększać przy każdym kroku. Dlatego w takiej metodzie zmniejszaj pozostałą pracę, przechodząc do kolejnego poziomu, i sprawdzaj, czy wejście może zawierać skrajnie głęboką strukturę.
Przy rekurencji matematycznej działa podobna zasada: dla silni przypadkiem bazowym jest zero, a kolejne wywołania zmniejszają argument. Jeśli argument zamiast tego pozostaje taki sam albo rośnie, metoda nie zbliża się do wyniku. Prześledzenie kilku wywołań na kartce często ujawnia ten błąd szybciej niż samo patrzenie na kod.
Wybieraj rekurencję dla naturalnie zagnieżdżonych danych
Rekurencja dobrze pasuje do struktur, których elementy zawierają kolejne elementy tego samego rodzaju, takich jak drzewa składni czy katalogi z podfolderami. Kod może wtedy przypominać kształt danych. Przy prostym odliczaniu albo przetwarzaniu długiej listy pętla zwykle jest łatwiejsza do kontrolowania.
| Sytuacja | Możliwa przyczyna lub skutek | Co zrobić |
|---|---|---|
| Argument w wywołaniu nie zmienia się | Metoda może powtarzać ten sam stan bez końca | Dodaj warunek kończący i sprawdź, czy każde wywołanie zmniejsza problem |
| Dane są zagnieżdżone, a ich głębokość ograniczona | Każdy poziom odpowiada jednemu wywołaniu | Rekurencja może uprościć przejście po strukturze |
| Głębokość wejścia jest nieznana lub kontroluje ją użytkownik | Łańcuch wywołań może urosnąć aż do przepełnienia stosu | Rozważ pętlę i własny stos przechowujący elementy do odwiedzenia |
Przy nieznanej głębokości danych wybór jest dość prosty: jeśli każde wywołanie przechodzi do kolejnego poziomu wejścia, którego rozmiaru nie kontrolujesz, użyj jawnego stosu i pętli; jeśli struktura ma naturalną, ograniczoną głębokość, rekurencja może być czytelniejsza. Własny stos oznacza tu kolekcję elementów oczekujących na przetworzenie, a nie kolejne wywołania metody.
W C# nie zakładaj, że rekurencja sama zmieni się w pętlę
Każde aktywne wywołanie metody zajmuje miejsce na stosie wywołań, a przy powrocie musi jeszcze przekazać wynik dalej. Nie opieraj bezpieczeństwa na optymalizacji rekurencji ogonowej, czyli zamianie końcowego wywołania metody na skok podobny do pętli. Zachowanie takiej optymalizacji nie jest gwarancją, na której powinien polegać kod C#.
Dokumentacja Microsoft Learn opisuje System.StackOverflowException jako wyjątek związany zwykle z bardzo głęboką lub nieograniczoną rekurencją. Podaje też, że domyślnie proces jest kończony, a wyjątku nie da się obsłużyć zwykłym blokiem try/catch. Lepiej wykryć ryzyko przed uruchomieniem zbyt głębokiego przejścia, niż próbować ratować aplikację po przepełnieniu stosu.
Gdy potrzebujesz stosu jawnego, w .NET możesz użyć Stack z przestrzeni nazw System.Collections.Generic. Metody Push i Pop dodają element na wierzch i pobierają go z tej samej strony, więc para pętla plus Stack pozwala zachować kolejność działania podobną do rekurencji. W kodzie przeglądającym nieprzewidywalnie głębokie drzewa to rozsądny wybór.
Najpierw sprawdź drogę powrotną
Gdy czytasz metodę rekurencyjną, śledź ją od wywołania do przypadku bazowego, a potem z powrotem do pierwszego wyniku. Jeśli nie potrafisz wskazać, co zmienia się w każdym kroku i gdzie metoda się zatrzymuje, sama zwięzłość kodu nie jest zaletą.
Uważam, że rekurencja jest najlepsza wtedy, gdy odzwierciedla strukturę problemu i jej głębokość da się przewidzieć. W pozostałych przypadkach pętla ze stosem daje bardziej bezpośrednią kontrolę nad tym, ile pracy czeka na wykonanie.
