Rekurencja to technika w programowaniu, gdzie funkcja woła samą siebie w celu rozwiązania mniejszych fragmentów problemu. Proces ten kontynuowany jest do momentu, gdy osiągnięty zostanie przypadek bazowy, czyli najmniejszy możliwy fragment problemu, który jest na tyle prosty, że można go rozwiązać bezpośrednio.
Jest to często stosowane w problemach, które można podzielić na mniejsze, podobne do siebie podproblemy.
Przykład rekurencyjnej funkcji w Pythonie, która oblicza silnię liczby:
def silnia(n):
if n == 0 or n == 1: # przypadek bazowy
return 1
else:
return n * silnia(n - 1) # wywołanie rekurencyjne
print(silnia(5)) # Wypisze 120, ponieważ 5! = 5 * 4 * 3 * 2 * 1 = 120
W powyższym przykładzie, funkcja silnia() wywołuje samą siebie, obliczając silnię mniejszej liczby, aż do momentu, gdy n osiągnie wartość 0 lub 1, co stanowi przypadek bazowy. Wtedy zwraca wartość 1 i zaczyna „odwijanie” wywołań rekurencyjnych, mnożąc wartości zwrócone przez wywołania funkcji `silnia` przez wartości n dla każdego z tych wywołań.
Rekurencja w programowaniu może być użyteczna w różnych sytuacjach, zwłaszcza gdy problem można podzielić na mniejsze, podobne do siebie podproblemy. Oto kilka przykładów, kiedy można zastosować rekurencję:
1. Problem dziel i zwycięża: Rekurencja jest często używana w strategii „dziel i zwyciężaj”, gdzie problem dzieli się na mniejsze podproblemy o tej samej naturze, rozwiązuje je niezależnie, a następnie łączy wyniki. Przykłady to sortowanie przez scalanie (merge sort) czy wyszukiwanie binarne.
2. Drzewa i grafy: Rekurencja jest naturalnym narzędziem do przeglądania struktur danych takich jak drzewa i grafy. Na przykład, przeszukiwanie drzewa binarnego czy algorytmy takie jak przeszukiwanie w głąb (DFS) czy przeszukiwanie wszerz (BFS) często są implementowane rekurencyjnie.
3. Dynamiczne programowanie: Rekurencja jest kluczowa dla technik dynamicznego programowania, które polega na rozbiciu problemu na mniejsze podproblemy, rozwiązaniu tych podproblemów i wykorzystaniu tych rozwiązań do rozwiązania większego problemu. Przykłady to problem plecakowy czy problem najdłuższego wspólnego podciągu.
4. Matematyczne problemy: Rekurencja jest często stosowana do rozwiązywania problemów matematycznych, które mają naturalną definicję rekurencyjną, takich jak obliczanie silni, ciągu Fibonacciego czy obliczanie symbolu Newtona.
5. Backtracking (powrotne śledzenie): W problemach, gdzie trzeba znaleźć wszystkie możliwe rozwiązania, często stosuje się strategię backtracking. Przykłady to problem N Hetmanów czy problem generowania wszystkich permutacji danej sekwencji.
Jednak należy pamiętać, że choć rekurencja jest potężnym narzędziem, może również prowadzić do problemów, takich jak przekroczenie limitu stosu czy niewydajność, jeżeli nie jest stosowana z ostrożnością. Czasami iteracyjne rozwiązanie problemu może być bardziej efektywne.
