Dokumentacja C z przykładami: Rekurencja

Q: Czym jest rekurencja w C?

To funkcja, która wywołuje samą siebie, aby rozwiązać mniejszą wersję tego samego problemu. Każda funkcja rekurencyjna potrzebuje dwóch rzeczy: przypadku bazowego, który zwraca wynik bez dalszej rekurencji, oraz przypadku rekurencyjnego, który wyraźnie się do niego zbliża. Bez przypadku bazowego wywołania nigdy się nie kończą, a program pada z przepełnieniem stosu.

Q: Jak napisać funkcję silni w C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Przypadek bazowy obsługuje 0 i 1, a każde wywołanie rekurencyjne zmniejsza n o jeden, aż do niego dojdzie. Pamiętaj, że int przepełnia się przy 13!, więc dla większych wartości użyj unsigned long long.

Q: Dlaczego rekurencyjny Fibonacci jest w C tak wolny?

Bo fib(n) wywołuje fib(n-1) i fib(n-2), które w kółko przeliczają te same podproblemy. Liczba wywołań rośnie wykładniczo, więc fib(50) liczyłoby się latami. Przepisanie go na pętlę, która pamięta dwie ostatnie wartości, daje złożoność liniową i natychmiastowy wynik.

Q: Co powoduje przepełnienie stosu przy rekurencji w C?

Każde wywołanie zajmuje ramkę pamięci stosu na parametry i zmienne lokalne, a stos ma tylko kilka megabajtów. Brakujący lub nieosiągalny przypadek bazowy oznacza nieskończoną rekurencję i natychmiastową awarię. Nawet poprawna rekurencja, która schodzi na setki tysięcy poziomów, może wyczerpać stos.

Funkcja, która wywołuje samą siebie

Nic nie zabrania funkcji w C wywoływać samej siebie. Jej własna nazwa jest widoczna wewnątrz jej ciała, więc to jest poprawne:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* wywoluje sama siebie, ale nigdy sie nie zatrzymuje! */
}

Jest też zepsute. Wypisuje w nieskończoność, schodząc w liczby ujemne, aż program się wysypie. Brakuje przypadku bazowego: warunku, przy którym funkcja zwraca wynik bez wywoływania samej siebie.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* przypadek bazowy: stop */
        printf("Start!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* przypadek rekurencyjny: mniejszy problem */
}

int main(void) {
    countdown(5);
    return 0;
}

Każda funkcja rekurencyjna ma dokładnie te dwie części:

Przypadek bazowy: najmniejsze wejście, na które odpowiedź jest podana wprost, bez kolejnego wywołania.
Przypadek rekurencyjny: rozwiązuje problem za pomocą ściśle mniejszej wersji samego siebie.

„Ściśle mniejszej” to część, w której ludzie się mylą. countdown(n - 1) z każdym wywołaniem zbliża się do 0. countdown(n) by się nie zbliżało, podobnie jak countdown(n / 2), gdyby n mogło w nieskończoność wynosić 1. Każda ścieżka musi zmniejszać problem, inaczej przypadek bazowy nigdy nie zostanie osiągnięty.

Silnia

Standardowy pierwszy przykład. n! to n × (n-1) × ... × 1, a 0! z definicji wynosi 1. Ta definicja już jest rekurencyjna: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* przypadek bazowy: 0! i 1! to 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* przypadek rekurencyjny */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

Prześledź factorial(4), żeby zobaczyć, jak składa się odpowiedź. Wywołania schodzą w dół, a mnożenia odbywają się w drodze powrotnej:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (przypadek bazowy)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

Nic nie jest mnożone, dopóki przypadek bazowy nie zwróci wyniku. Każde oczekujące wywołanie czeka, trzymając własne n, i to warto sobie przyswoić: te czekające wywołania zajmują pamięć.

Zwróć uwagę na typ zwracany. int przepełnia się w okolicach 13! i po cichu daje złą liczbę, bo C tego nie sprawdza. unsigned long long doprowadzi cię do 20! i ani kroku dalej, bo 21! przekracza 64 bity. Ograniczeniem nie jest tu rekurencja, tylko typ.

Przypadek bazowy celowo używa n <= 1 zamiast n == 1: factorial(0) powinno dać 1, a <= to obsługuje. Przy n == 1 wywołanie factorial(0) schodziłoby do -1, -2 i nigdy by się nie zakończyło. To dobry przykład na to, jak „oczywiście poprawny” przypadek bazowy może pominąć jakieś wejście.

Fibonacci i dlaczego naiwna wersja to pułapka

Fibonacci to drugi klasyk: każda liczba jest sumą dwóch poprzednich, zaczynając od 0 i 1. Definicja rekurencyjna pisze się sama.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (wywolan: %lld)\n", n, result, calls);
    }
    return 0;
}

Spójrz na liczbę wywołań. fib(10) potrzebuje 177 wywołań, a fib(35) prawie 30 milionów. Każdy krok o 5 mnoży pracę mniej więcej jedenaście razy.

Przyczynę widać w drzewie wywołań. fib(5) wywołuje fib(4) i fib(3), fib(4) znowu wywołuje fib(3), a każde z nich od zera przelicza fib(2). Nic nie jest zapamiętywane, więc te same podproblemy są rozwiązywane raz za razem, a liczba wywołań rośnie mniej więcej jak 1,6ⁿ. fib(50) liczone w ten sposób trwałoby dniami, a fib(100) przetrwałoby wszechświat.

Wersja z pętlą pamięta dwie ostatnie wartości i działa liniowo:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) zwraca wynik natychmiast. Lekcja nie brzmi „rekurencja jest wolna”, tylko: rekurencja z nakładającymi się podproblemami jest wolna, chyba że zapamiętujesz odpowiedzi. Zapisuj wyniki w tablicy w miarę ich liczenia (memoizacja), a wersja rekurencyjna też stanie się liniowa.

Stos wywołań i przepełnienie stosu

Każde wywołanie funkcji potrzebuje miejsca na parametry, zmienne lokalne i adres powrotu. To miejsce to ramka stosu, odkładana na stos, gdy wywołanie się zaczyna, i zdejmowana, gdy się kończy. Rekurencja układa ramki jedna na drugiej: factorial(1000) ma jednocześnie tysiąc aktywnych ramek, każdą z własnym n.

Stos nie jest duży. Typowa wartość domyślna to 1-8 MB, więc realny limit to kilkadziesiąt tysięcy ramek, a znacznie mniej, jeśli każda ramka trzyma dużą lokalną tablicę. Przekrocz go, a program zginie:

Segmentation fault (core dumped)

To przepełnienie stosu (stack overflow), a można do niego dojść na dwa sposoby:

Nieskończona rekurencja: brakujący lub nieosiągalny przypadek bazowy. To błąd, a awaria następuje natychmiast:

int bad(int n) {
    return bad(n - 1);      /* brak przypadku bazowego: pada w ulamku sekundy */
}

Poprawna, ale za głęboka: rekurencja raz na element listy z milionem elementów. Logika jest dobra, ale to podejście nie mieści się na stosie. Przepisz je na pętlę albo zmień strukturę tak, by głębokość była logarytmiczna (rekurencja na połówkach, jak w wyszukiwaniu binarnym i sortowaniu przez scalanie, daje głębokość około 20 dla miliona elementów).

Niektóre kompilatory potrafią zamienić rekurencję ogonową, czyli taką, w której wywołanie rekurencyjne jest ostatnią czynnością funkcji i nic po nim nie zostaje do zrobienia, na pętlę z jedną, ponownie używaną ramką. Powyższe countdown jest rekurencyjne ogonowo, a factorial nie, bo mnożenie musi się odbyć po powrocie z wywołania. Ale C nie wymaga tej optymalizacji, więc może się ona pojawić albo nie, zależnie od kompilatora i flag. Nigdy nie pisz w C kodu, który działa tylko dlatego, że optymalizator usunął wywołanie ogonowe.

Gdzie rekurencja naprawdę wygrywa

Każdą funkcję rekurencyjną da się przepisać na pętlę, a przy prostym liczeniu pętla jest po prostu lepsza. Rekurencja pokazuje swoją wartość wtedy, gdy same dane są rekurencyjne, czyli gdy struktura zawiera mniejsze kopie samej siebie.

Wyszukiwanie binarne to czysty przykład: przeszukaj połowę, potem połowę tej połowy.

#include <stdio.h>

/* zwraca indeks target albo -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* przypadek bazowy: nic nie zostalo */
    }
    int mid = low + (high - low) / 2;       /* unika przepelnienia przy duzych indeksach */

    if (a[mid] == target) {
        return mid;                         /* przypadek bazowy: znaleziono */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> indeks %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

Są tu dwa przypadki bazowe i to normalne: jeden na sukces, drugi na wyczerpanie zakresu. Głębokość wynosi około log₂(n), więc nawet miliard elementów potrzebuje tylko trzydziestu ramek.

Inne miejsca, w których rekurencja pasuje naturalnie: przechodzenie drzewa lub listy wiązanej, przeglądanie katalogów, parsowanie zagnieżdżonych wyrażeń i sortowania typu dziel i zwyciężaj, takie jak quicksort i merge sort. We wszystkich tych przypadkach kod rekurencyjny jest krótszy i czytelniejszy niż zastępująca go pętla z jawnym stosem.

Rekurencja czy pętla?

Uzyj petli, gdy             problem jest liniowy: liczenie, sumowanie, przegladanie
Uzyj rekurencji, gdy        dane sa zagniezdzone: drzewa, struktury zagniezdzone, dziel i zwyciezaj
Przepisz rekurencje,        jesli glebokosc moze rosnac bez ograniczen wraz z rozmiarem wejscia
Nie uzywaj rekurencji,      gdy podproblemy sie nakladaja, chyba ze stosujesz memoizacje

Dwie praktyczne uwagi. Wywołania rekurencyjne kosztują trochę więcej niż iteracja pętli, bo za każdym razem trzeba odłożyć i zdjąć ramkę, więc przy gorących, prostych pętlach wersja iteracyjna wygrywa zarówno szybkością, jak i pamięcią. Inaczej wygląda też debugowanie: ślad stosu z głębokiej rekurencji to setki identycznie wyglądających ramek, więc gdy coś się nie kończy, wypisuj parametr na wejściu do funkcji (tak jak robi to licznik calls powyżej).

Pisanie funkcji rekurencyjnej: lista kontrolna

Najpierw znajdź przypadek bazowy. Jakie jest najmniejsze wejście i jaka jest dla niego odpowiedź? Jeśli nie potrafisz go nazwać, funkcji nie da się napisać.
Załóż, że wywołanie rekurencyjne działa. Nie śledź go w głowie: zaufaj, że factorial(n - 1) zwraca (n-1)!, i napisz ten jeden krok, który zamienia to w odpowiedź.
Sprawdź, czy każda ścieżka zmniejsza problem. Każde wywołanie rekurencyjne musi zbliżać się do przypadku bazowego dla każdego możliwego wejścia, w tym 0 i liczb ujemnych.
Sprawdź głębokość. Na ile ramek w głąb zejdzie to mniej więcej na prawdziwych danych? Tysiące są w porządku, miliony nie.
Sprawdź nakładanie się. Jeśli ten sam podproblem jest liczony dwa razy, potrzebujesz memoizacji albo pętli.

Najczęściej zadawane pytania

Czym jest rekurencja w C?

To funkcja, która wywołuje samą siebie, aby rozwiązać mniejszą wersję tego samego problemu. Każda funkcja rekurencyjna potrzebuje dwóch rzeczy: przypadku bazowego, który zwraca wynik bez dalszej rekurencji, oraz przypadku rekurencyjnego, który wyraźnie się do niego zbliża. Bez przypadku bazowego wywołania nigdy się nie kończą, a program pada z przepełnieniem stosu.

Jak napisać funkcję silni w C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Przypadek bazowy obsługuje 0 i 1, a każde wywołanie rekurencyjne zmniejsza n o jeden, aż do niego dojdzie. Pamiętaj, że int przepełnia się przy 13!, więc dla większych wartości użyj unsigned long long.

Dlaczego rekurencyjny Fibonacci jest w C tak wolny?

Bo fib(n) wywołuje fib(n-1) i fib(n-2), które w kółko przeliczają te same podproblemy. Liczba wywołań rośnie wykładniczo, więc fib(50) liczyłoby się latami. Przepisanie go na pętlę, która pamięta dwie ostatnie wartości, daje złożoność liniową i natychmiastowy wynik.

Co powoduje przepełnienie stosu przy rekurencji w C?

Każde wywołanie zajmuje ramkę pamięci stosu na parametry i zmienne lokalne, a stos ma tylko kilka megabajtów. Brakujący lub nieosiągalny przypadek bazowy oznacza nieskończoną rekurencję i natychmiastową awarię. Nawet poprawna rekurencja, która schodzi na setki tysięcy poziomów, może wyczerpać stos.

Powiązane zagadnienia