Rekurencja to jeden z fundamentalnych konceptów programowania, który pozwala funkcji wywoływać samą siebie. W teorii programowania i algorytmach rekurencja jest używana do rozwiązywania problemów, które można podzielić na mniejsze, podobne do siebie podproblemy. Mechanizm ten jest nie tylko potężnym narzędziem, ale także stanowi podstawę wielu algorytmów, w szczególności w dziedzinach takich jak sortowanie, przeszukiwanie struktur danych, a także w problemach matematycznych. Zrozumienie działania rekurencji wymaga dobrej znajomości zarówno teorii, jak i praktycznych przykładów, które pozwalają na łatwiejsze przyswojenie tej koncepcji.

Podstawy rekurencji

W języku C++ funkcja rekurencyjna to funkcja, która wywołuje samą siebie, bezpośrednio lub pośrednio. Każda funkcja rekurencyjna musi mieć dwa kluczowe elementy:

• Przypadek bazowy: Jest to warunek zakończenia rekurencji, który zapobiega nieskończonemu wywoływaniu funkcji. Przypadek bazowy określa, kiedy funkcja ma przestać wywoływać samą siebie i zwrócić wynik.
• Wywołanie rekurencyjne: To część funkcji, która wywołuje samą siebie z nowymi argumentami, które prowadzą do osiągnięcia przypadku bazowego.

Kluczowe znaczenie ma to, aby przypadek bazowy był osiągalny i aby każde wywołanie rekurencyjne przybliżało funkcję do tego przypadku bazowego. W przeciwnym razie rekurencja może prowadzić do nieskończonego wywołania funkcji, co skutkuje przepełnieniem stosu (ang. *stack overflow*).

Prosty przykład: Silnia

Silnia liczby całkowitej n, oznaczana jako n!, jest iloczynem wszystkich liczb całkowitych od 1 do n. Definicja rekurencyjna silni wygląda następująco:

• 0! = 1 (przypadek bazowy)
• n! = n * (n - 1)! dla n > 0

Oto przykład funkcji rekurencyjnej w C++, która oblicza silnię:

#include <iostream>

int silnia(int n) {
    if (n == 0) {
        return 1; // Przypadek bazowy
    } else {
        return n * silnia(n - 1); // Wywołanie rekurencyjne
    }
}

int main() {
    int liczba = 5;
    std::cout << "Silnia " << liczba << " wynosi: " << silnia(liczba) << std::endl;
    return 0;
}

W tym przykładzie przypadek bazowy to n == 0, który zwraca wartość 1. Wywołanie rekurencyjne zmniejsza wartość n o 1, co ostatecznie prowadzi do przypadku bazowego. Każde wywołanie rekurencyjne jest dodawane do stosu wywołań, a po osiągnięciu przypadku bazowego wywołania są rozwiązywane w odwrotnej kolejności.

Stos wywołań i przepełnienie stosu

Podczas gdy funkcje rekurencyjne są wywoływane, informacje o każdej z nich (takie jak argumenty, lokalne zmienne i miejsce powrotu) są przechowywane na stosie wywołań. Kiedy funkcja osiągnie przypadek bazowy, jej wynik jest zwracany, a stos wywołań jest „odwijany”, zwracając wyniki kolejnych funkcji w odwrotnej kolejności, w jakiej były wywoływane. Jeśli przypadek bazowy nie zostanie osiągnięty lub rekurencja jest zbyt głęboka, stos może się przepełnić, co prowadzi do błędu znanego jako przepełnienie stosu (ang. *stack overflow*).

Przykład nieskończonej rekurencji

#include <iostream>

void nieskonczonaRekurencja() {
    std::cout << "To się nigdy nie skończy!" << std::endl;
    nieskonczonaRekurencja(); // Brak przypadku bazowego
}

int main() {
    nieskonczonaRekurencja();
    return 0;
}

W powyższym przykładzie funkcja nieskonczonaRekurencja nie ma przypadku bazowego, co prowadzi do nieskończonych wywołań rekurencyjnych i ostatecznie do przepełnienia stosu. Dlatego zawsze należy upewnić się, że przypadek bazowy istnieje i jest osiągalny.

Typowe zastosowania rekurencji

Rekurencja jest szeroko stosowana w algorytmach i strukturach danych, szczególnie tam, gdzie problemy można podzielić na mniejsze, podobne do siebie części. Oto kilka typowych zastosowań rekurencji:

1. Przeszukiwanie drzew i grafów

Drzewa i grafy to struktury danych, które naturalnie nadają się do rozwiązania za pomocą rekurencji. Na przykład algorytmy takie jak przeszukiwanie w głąb (DFS) korzystają z rekurencji, aby przechodzić przez wszystkie węzły drzewa lub grafu.

#include <iostream>
#include <vector>

class Wezel {
public:
    int wartosc;
    std::vector<Wezel*> dzieci;

    Wezel(int wartosc) : wartosc(wartosc) {}

    void dodajDziecko(Wezel* dziecko) {
        dzieci.push_back(dziecko);
    }

    void przeszukaj() {
        std::cout << "Węzeł: " << wartosc << std::endl;
        for (Wezel* dziecko : dzieci) {
            dziecko->przeszukaj(); // Wywołanie rekurencyjne
        }
    }
};

int main() {
    Wezel* korzen = new Wezel(1);
    Wezel* dziecko1 = new Wezel(2);
    Wezel* dziecko2 = new Wezel(3);
    korzen->dodajDziecko(dziecko1);
    korzen->dodajDziecko(dziecko2);

    korzen->przeszukaj();

    delete korzen;
    delete dziecko1;
    delete dziecko2;
    return 0;
}

W tym przykładzie metoda przeszukaj wywołuje samą siebie dla każdego dziecka węzła, co umożliwia przeszukiwanie drzewa w głąb.

2. Sortowanie (np. QuickSort, MergeSort)

Algorytmy sortowania, takie jak QuickSort i MergeSort, są przykładami efektywnego wykorzystania rekurencji. Te algorytmy dzielą problem na mniejsze podproblemy, które są następnie rozwiązywane rekurencyjnie.

#include <iostream>
#include <vector>

void quickSort(std::vector<int>& vec, int left, int right) {
    if (left >= right) return; // Przypadek bazowy

    int pivot = vec[right];
    int partitionIndex = left;
    for (int i = left; i < right; ++i) {
        if (vec[i] <= pivot) {
            std::swap(vec[i], vec[partitionIndex]);
            partitionIndex++;
        }
    }
    std::swap(vec[partitionIndex], vec[right]);

    quickSort(vec, left, partitionIndex - 1); // Lewa strona
    quickSort(vec, partitionIndex + 1, right); // Prawa strona
}

int main() {
    std::vector<int> liczby = {3, 6, 8, 10, 1, 2, 1};
    quickSort(liczby, 0, liczby.size() - 1);

    for (int liczba : liczby) {
        std::cout << liczba << " ";
    }
    std::cout << std::endl;
    return 0;
}

W algorytmie QuickSort funkcja rekurencyjnie dzieli tablicę na mniejsze części, które są następnie sortowane, aż osiągnięty zostanie przypadek bazowy (kiedy lewy indeks jest większy lub równy prawemu).

Rekurencja vs. iteracja

W wielu przypadkach problemy, które można rozwiązać rekurencyjnie, można również rozwiązać iteracyjnie. Wybór między rekurencją a iteracją zależy od konkretnych wymagań i ograniczeń danego problemu:

• Rekurencja: Często prowadzi do bardziej eleganckiego i zwięzłego kodu, szczególnie w przypadku problemów, które można łatwo podzielić na podproblemy. Jednak rekurencja może być mniej wydajna pod względem zużycia pamięci, ponieważ każde wywołanie funkcji zajmuje miejsce na stosie.
• Iteracja: Zwykle bardziej wydajna pod względem pamięci, ponieważ nie wymaga dodatkowych ramek stosu. Jednak iteracyjne rozwiązania mogą być bardziej złożone i mniej intuicyjne dla niektórych problemów.

Przykład: Obliczanie ciągu Fibonacciego

Rozważmy problem obliczania n-tego wyrazu ciągu Fibonacciego:

#include <iostream>

// Rekurencyjne rozwiązanie
int fibonacciRekurencyjnie(int n) {
    if (n <= 1) return n; // Przypadki bazowe
    return fibonacciRekurencyjnie(n - 1) + fibonacciRekurencyjnie(n - 2);
}

// Iteracyjne rozwiązanie
int fibonacciIteracyjnie(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 10;
    std::cout << "Fibonacci (rekurencyjnie): " << fibonacciRekurencyjnie(n) << std::endl;
    std::cout << "Fibonacci (iteracyjnie): " << fibonacciIteracyjnie(n) << std::endl;
    return 0;
}

W rekurencyjnym rozwiązaniu każda liczba Fibonacciego jest obliczana wiele razy, co prowadzi do znacznej nieefektywności. Iteracyjne rozwiązanie jest bardziej wydajne, ale mniej intuicyjne.

Podsumowanie

Rekurencja to potężne narzędzie, które pozwala rozwiązywać złożone problemy w elegancki i intuicyjny sposób. Jednak jej użycie wymaga ostrożności, aby unikać nieskończonych wywołań i przepełnienia stosu. W tej lekcji omówiliśmy, jak działa rekurencja, jak definiować przypadki bazowe oraz jakie są typowe zastosowania tego mechanizmu. Zrozumienie różnic między rekurencją a iteracją oraz znajomość technik optymalizacji rekurencyjnych rozwiązań pozwala na lepsze wykorzystanie tego narzędzia w codziennej pracy programisty.

Następny temat ==> Wyrażanie problemów za pomocą rekurencji