Odpowiedź.

Historia pytania
Rekurencja jako mechanizm jest często stosowana do eleganckiego rozwiązywania problemów związanych z przeszukiwaniem drzew, obliczaniem silni, szybkim sortowaniem. W C wywołania rekurencyjne są realizowane bezpośrednio, ponieważ funkcja może wywoływać samą siebie poprzez standardowe odniesienie po nazwie.

Problem
Rekurencja jest wygodna, ale niesie ze sobą ryzyko szybkiego przepełnienia stosu w wyniku głębokiej zagnieżdżenia (stack overflow). Ponadto działa nieefektywnie dla dużych danych wejściowych bez optymalizacji (na przykład z powodu braku rekurencji ogonowej).

Rozwiązanie
Przed zastosowaniem rekurencji należy sprawdzić maksymalną możliwą głębokość, wdrożyć warunki brzegowe (base case), rozważyć zużycie pamięci (stosu), a w krytycznych przypadkach — przepisać algorytm na wariant iteracyjny.

Przykład kodu:

// Obliczanie silni rekurencyjnie
unsigned long factorial(unsigned int n) {
    if (n <= 1) return 1;   // przypadek bazowy
    return n * factorial(n - 1);  // przypadek rekurencyjny
}

Kluczowe cechy:

Przy każdym wywołaniu tworzona jest nowa kopia zmiennych lokalnych na stosie
Niezbędna jest kontrola przypadków bazowych, aby uniknąć nieskończonej rekurencji
Rekurencję łatwo zaimplementować, ale trudno optymalizować dla rzeczywistych dużych danych

Pytania z podstępem.

Czy funkcja w C może bezpośrednio wywołać siebie pod dowolną nazwą?

Nie. Funkcja wywołuje tylko siebie, używając swojej własnej nazwy, która musi być zdefiniowana w momencie wywołania (lub przynajmniej wcześniej zadeklarowana).

Czy rekurencja zawsze jest wydajniejsza niż pętla?

Nie! Rozwiązania iteracyjne często działają szybciej i bardziej niezawodnie, ponieważ nie zużywają szybko stosu i nie wymagają dodatkowych kosztów związanych z wywołaniami funkcji.

Czy po rekurencji stos wraca do pierwotnego stanu?

Tak, stos jest całkowicie zwalniany po wyjściu z każdej funkcji rekurencyjnej. Po zakończeniu najbardziej zewnętrznej funkcji pamięć wraca do poprzedniego stanu.

Typowe błędy i antywzorce

Brak przypadku bazowego (base case), prowadzi do nieskończonej rekurencji
Pomylenie warunków wyjścia z rekurencji
Zastosowanie rekurencji tam, gdzie bardziej efektywna jest pętla

Przykład z życia

Negatywny przypadek

Programista zaimplementował funkcję przeszukiwania drzewa za pomocą rekurencji dla 100 000 węzłów bez sprawdzania głębokości. Wystąpił stack overflow.

Zalety:

Prosty i zwięzły kod Wady:
Aplikacja pada przy dużej ilości danych z powodu przepełnienia stosu

Pozytywny przypadek

Algorytm został zaimplementowany z monitorowaniem głębokości rekurencji i zabezpieczeniem przed zbyt głębokim zagnieżdżeniem, duże przejścia są dzielone na partie (wariant iteracyjny).