Funkcje rekurencyjne w C++
1. Definicja rekurencji
Rekurencja to technika programistyczna, w której funkcja wywołuje samą siebie, aby rozwiązać mniejsze podproblemy danego zadania. Problem zostaje podzielony na prostsze wersje samego siebie, aż do osiągnięcia warunku brzegowego (ang. base case), który kończy wywołania rekurencyjne.
2. Struktura funkcji rekurencyjnej
Każda funkcja rekurencyjna musi zawierać dwa kluczowe elementy:
Warunek brzegowy (zakończenia)
- Określa, kiedy funkcja ma przestać wywoływać samą siebie.
- Zapobiega nieskończonej rekurencji.
Wywołanie rekurencyjne
- Funkcja odwołuje się do samej siebie, ale z prostszym argumentem.
Schemat:
3. Przykłady
3.1. Obliczanie silni (n!)
Silnia to klasyczny przykład rekurencji.
Wywołania:
silnia(4) = 4 * 3 * 2 * 1 * 1
3.2. Ciąg Fibonacciego
Każdy element to suma dwóch poprzednich:
Uwaga: ta wersja jest bardzo nieefektywna (złożoność O(2ⁿ)).
3.3. Rekurencyjne przeszukiwanie tablicy
Przykład: znajdź maksymalny element.
4. Typy rekurencji
➤ Rekurencja prosta (jednowątkowa)
Funkcja wywołuje się tylko raz:
➤ Rekurencja wielokrotna (np. Fibonacciego)
➤ Rekurencja ogonowa (tail recursion)
Wywołanie rekurencyjne jest ostatnią instrukcją:
Teoretycznie kompilator mógłby ją zoptymalizować, ale C++ nie gwarantuje TCO (Tail Call Optimization).
➤ Rekurencja pośrednia
Funkcja wywołuje inną, a ta znowu poprzednią:
5. Zastosowania rekurencji
Rekurencja jest szczególnie użyteczna tam, gdzie naturalnie występuje struktura „podproblemów”:
Struktury drzewiaste
- przeszukiwanie drzewa
- operacje na drzewach binarnych
- przechodzenie katalogów w systemie plików
Algorytmy klasyczne
- sortowanie szybkie (quicksort)
- sortowanie przez scalanie (mergesort)
- algorytm Euklidesa
Matematyka
- silnia, potęgowanie szybkie
- liczby Fibonacciego
- równania rekurencyjne
6. Złożoność czasowa
Rekurencja może być bardziej kosztowna niż iteracja:
- każde wywołanie funkcji zajmuje czas i miejsce na stosie
- funkcja Fibonacciego ma wykładniczą złożoność
- można to optymalizować memoizacją lub DP
Porównanie (na przykładzie silni):
- rekurencja: O(n), zużycie stosu: O(n)
- iteracja: O(n), zużycie stosu: O(1)
7. Typowe błędy
brak warunku brzegowego
Prowadzi do przepełnienia stosu.
zbyt wolna rekurencja
Np. Fibonacciego bez optymalizacji.
zbyt głęboka rekurencja
Domyślna głębokość stosu może wynosić np. ~10 000 wywołań — przy dużych wartościach należy użyć iteracji.
niepoprawna redukcja argumentu
Argument musi z każdą iteracją być „bliżej” warunku brzegowego.
8. Alternatywy dla rekurencji
Iteracja
Zwykle szybsza i bezpieczniejsza.
Memoizacja
Przechowywanie wyników:
Programowanie dynamiczne
Tablicowe rozwiązania bottom-up.
9. Podsumowanie
Funkcje rekurencyjne są:
- eleganckie i często bardziej intuicyjne niż iteracja,
- szczególnie przydatne w strukturach drzewiastych i algorytmach dziel-i-zwyciężaj,
-
ale mogą być:
- wolniejsze,
- bardziej pamięciożerne,
- narażone na przepełnienie stosu.
Rekurencję warto stosować rozważnie — tam, gdzie jej użycie upraszcza kod lub jest naturalnym odzwierciedleniem problemu.