Algorytmy rekurencyjne

1.Rekurencja

Sposób definiowania algorytmu lub funkcji, w którym odwołuje się ona do samej siebie dla mniejszych lub prostszych danych. Aby działała poprawnie, musi prowadzić do zakończenia po skończonej liczbie kroków.

2.Przypadek bazowy

Warunek kończący działanie rekurencji. Dla najprostszego argumentu funkcja zwraca wynik bez dalszych wywołań. Brak przypadku bazowego zwykle prowadzi do nieskończonej rekurencji.

3.Krok rekurencyjny

Część algorytmu, w której problem jest sprowadzany do mniejszego podproblemu i następuje kolejne wywołanie funkcji. Powinien przybliżać obliczenie do przypadku bazowego.

4.Stos wywołań

Struktura pamięci, na której zapisywane są kolejne aktywne wywołania funkcji: argumenty, zmienne lokalne i adres powrotu. Przy zbyt głębokiej rekurencji może dojść do przepełnienia stosu.

5.Przepełnienie stosu

Błąd powstający wtedy, gdy liczba zagnieżdżonych wywołań jest zbyt duża dla dostępnej pamięci stosu. Często wynika z braku poprawnego warunku zakończenia albo zbyt głębokiej rekurencji.

6.Rekurencja bezpośrednia

Sytuacja, w której funkcja wywołuje samą siebie wprost, np. funkcja silni wywołuje silnię dla mniejszego argumentu.

7.Rekurencja pośrednia

Sytuacja, w której funkcja nie wywołuje siebie od razu, lecz przez inną funkcję, np. $f()$ wywołuje $g()$, a $g()$ wywołuje $f()$.

8.Rekurencja ogonowa

Rodzaj rekurencji, w której wywołanie rekurencyjne jest ostatnią operacją funkcji. W niektórych językach może to ułatwiać optymalizację i zmniejszać zużycie pamięci.

9.Iteracja a rekurencja

Iteracja powtarza operacje za pomocą pętli, a rekurencja przez kolejne wywołania funkcji. Obie metody mogą rozwiązywać ten sam problem, ale różnią się sposobem zapisu i użyciem pamięci.

10.Drzewo wywołań

Schemat pokazujący wszystkie wywołania rekurencyjne powstające podczas działania algorytmu. Pomaga analizować liczbę operacji, zwłaszcza przy rekurencji wielokrotnej, np. w ciągu Fibonacciego.

11.Złożoność czasowa rekurencji

Opisuje, jak liczba operacji rośnie wraz z rozmiarem danych. W algorytmach rekurencyjnych zależy od liczby wywołań i pracy wykonywanej w każdym z nich, np. może wynosić $O(n)$ albo $O(2^n)$.

12.Złożoność pamięciowa rekurencji

Określa ilość pamięci potrzebnej do działania algorytmu. W rekurencji często zależy od maksymalnej głębokości stosu wywołań, np. dla prostego schodzenia o $1$ może wynosić $O(n)$.

13.Silnia rekurencyjnie

Klasyczny przykład: $n! = n \cdot (n-1)!$ dla $n>0$ oraz $0! = 1$. Pokazuje połączenie przypadku bazowego i kroku rekurencyjnego.

14.Ciąg Fibonacciego rekurencyjnie

Definicja: $F_0=0$, $F_1=1$, a dla większych indeksów $F_n=F_{n-1}+F_{n-2}$. Prosta implementacja rekurencyjna jest czytelna, ale ma zwykle słabą wydajność.