Odpowiedź.

Historia pytania:

Rekurencja jest obsługiwana w C od jego powstania — naturalnie wpisuje się w paradygmat języka, umożliwiając tworzenie kompaktowych rozwiązań, szczególnie do zadań związanych z drzewami, listami, złożonymi algorytmami podziału.

Problem:

Główne ryzyka związane z używaniem rekurencji to nadmierne zużycie stosu, możliwość przepełnienia stosu (stack overflow) oraz nieoczywisty wpływ na wydajność (w porównaniu do realizacji opartej na pętli). W C nie ma standardowego sposobu automatycznego kontrolowania głębokości zagnieżdżenia wywołań.

Rozwiązanie:

Przed zastosowaniem rekurencji należy ocenić maksymalny możliwy poziom zagnieżdżenia, używać rekurencji ogonowej, jeśli to możliwe (dla optymalizacji przez kompilator), oraz dodawać mechanizmy ochrony przed przepełnieniem, na przykład jawny licznik głębokości rekurencji. Alternatywną metodą jest zastępowanie wywołań rekurencyjnych pętlami dla prostych zadań.

Przykład kodu:

#include <stdio.h>
#define MAX_DEPTH 1000

int factorial(int n, int depth) {
    if (depth > MAX_DEPTH) {
        printf("Błąd: maksymalna głębokość rekurencji została przekroczona!\n");
        return -1;
    }
    if (n == 0) return 1;
    return n * factorial(n - 1, depth + 1);
}

int main() {
    printf("%d\n", factorial(5, 0)); // 120
    return 0;
}

Kluczowe cechy:

• Brak gwarancji automatycznego ograniczenia głębokości rekurencji
• Rekurencja zużywa stos, który może być ograniczony
• Rekurencja ogonowa może być optymalizowana przez kompilator, ale nie zawsze

Pytania z haczykiem.

Czy stos zostanie oczyszczony, jeśli w obrębie funkcji rekurencyjnej nastąpi return przed zakończeniem wszystkich wywołań?

Tak, stos jest zwalniany przy wyjściu z bieżącej funkcji. Żadne „wiszące” dane na stosie nie pozostaną, jeśli stos nie został przepełniony.

Czy można deklarować wewnątrz ciała funkcji rekurencyjnej statyczne zmienne lokalne i jak będą się one zachowywać?

Można. Takie zmienne będą wspólne dla wszystkich wywołań rekurencyjnych, ich wartość zostanie zachowana między wywołaniami, co często prowadzi do błędów, jeśli nie uwzględnia się tego zachowania.

Czy kompilator C wpływa na głębokość rekurencji i może ją ograniczyć?

Kompilator bezpośrednio nie ogranicza rekurencji. Głębokość rekurencji jest ograniczona rozmiarem stosu systemu operacyjnego lub czynnikami zewnętrznymi.

Typowe błędy i antywzorce

• Nieograniczona rekurencja bez kontroli głębokości
• Nieinicjowane lub statyczne zmienne lokalne w ciele funkcji rekurencyjnej
• Używanie rekurencji tam, gdzie prostsza i efektywniejsza jest pętla

Przykład z życia

Zrealizowano rekurencyjne przeszukiwanie drzewa binarnego bez ograniczenia głębokości:

Zalety:

• Kod jest zwięzły, łatwy do odczytania

Wady:

• Przy dużej głębokości drzewa program kończył się błędem przepełnienia stosu.

W poprawionej wersji wprowadzono licznik głębokości i przejście do przeszukiwania opartego na stosie przy dużych rozmiarach drzewa:

Zalety:

• Program działa poprawnie na wszystkich danych wejściowych

Wady:

• Kod stał się bardziej złożony, wymagał dodatkowego testowania