Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu oraz w matematyce odwoływanie się np. funkcji albo definicji do samej siebie.
W logice wnioskowanie rekurencyjne ma za podstawę na założeniu istnienia pewnego stanu początkowego oraz zdania (lub zdań) stanowiącego podstawę wnioskowania (przy czym aby cały dowód był poprawny zarówno reguła jak oraz stan początkowy muszą być prawdziwe). Istotą rekurencji jest tożsamość dziedziny oraz przeciwdziedziny reguły wnioskowania, wskutek czego wynik wnioskowania może podlegać tej samej regule zastosowanej ponownie.
Na prostym przykładzie:
reguła: każdy ojciec jest starszy od swojego syna; każdy ojciec jest czyimś synem
stan początkowy: jestem 22-letnim mężczyzną
teza: ojciec ojca mojego ojca jest starszy ode mnie
dowód:
- mój ojciec jest starszy ode mnie
- mój ojciec jest czyimś synem
- ojciec mojego ojca jest starszy od mojego ojca
- ojciec mojego ojca jest czyimś synem
- itd.
Na przykładzie zastosowań matematycznych poniższa definicja ciągu Fibonacciego jest rekurencyjna:


, dla 
gdyż definiuje funkcję odwołując się w definicji do niej samej.
Każda definicja rekurencyjna potrzebuje przynajmniej jednego przypadku bazowego (nie rekurencyjnego), w tym przypadku są to wartości dla 0 oraz 1. W przeciwnym wypadku wcale się nie zakończy.
Dla przykładu, obliczenie
wygląda następująco:


Innym przykładem jest wyliczanie największego wspólnego dzielnika za pomocą algorytmu Euklidesa:
,
dla
oznacza tu resztę z dzielenia
przez 
lub inaczej:

Rekurencja jest podstawową techniką wykorzystywaną w funkcyjnych językach programowania. Należy jednak zachować ostrożność przy używaniu rekurencji w rzeczywistych programach. Ryzyko istnieje szczególnie przy przetwarzaniu dużej ilości głęboko zagnieżdżonych danych.
Jeśli program nie jest w rzeczywistości rekurencyjny, to rekurencja może dramatycznie zwiększyć złożoność obliczeniową. Ponadto rekurencja stale zwiększa pamięciowe zapotrzebowanie programu (chyba że zostanie użyta możliwa w pewnych przypadkach optymalizacja zwana rekursją ogonową), albowiem wymaga ona zapamiętania m.in. adresów powrotu, pozwalających programowi "zorientować się" do którego miejsca ma wrócić po zakończeniu jednego z wywołań rekurencyjnych. Inną częstą wadą rekurencji jest kompletnie niezależne rozwiązywanie podproblemów, tak, że czasem jeden problem jest rozwiązywany w kilku miejscach rozwinięcia rekurencji, np. w powyższym przykładzie obliczania
niepotrzebnie jest dwukrotnie obliczana wartość
(porównaj: programowanie dynamiczne). Takie problemy nie pojawiają się przy drugim z przykładów. Niezaprzeczalną zaletą rekurencji jest przejrzystość programów, które z niej korzystają.
Jedną z typowych sytuacji, w których stosuje się rekurencję jest przeszukiwanie danych o strukturze nieregularnego drzewa, np. XML. Funkcja, która sprawdza czy w danym obiekcie XML istnieje element o określonej zawartości mogłaby wyglądać następująco (tutaj w PHP przy użyciu klasy SimpleXML):
function find_text($text, $tree) {
// sprawdź zawartość aktualnego elementu
if ($text == (string)$tree) {
return true;
}
// sprawdź wszystkie jego dzieci
foreach ($tree as $node) {
// tutaj następuje wywołanie rekurencyjne
if (find_text($text, $node)) {
return true;
}
}
// nic nie znaleziono
return false;
}
Przykłady
Sprawdź też