Rekurencja, rekursja (z łac. recurrere, przybiec z powrotem) – odwoływanie się funkcji lub definicji do samej siebie.

W logice wnioskowanie rekurencyjne opiera się 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 i stan początkowy muszą być prawdziwe). Istotą rekurencji jest tożsamość dziedziny i przeciwdziedziny reguły wnioskowania, wskutek czego wynik wnioskowania może podlegać tej samej regule zastosowanej ponownie.

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. Rekurencja może spowodować błąd przepełnienia stosu, chyba że język stosuje optymalizacje rekurencji ogonowej lub gdy stosuje się trampolinę.

W językach, w których nie ma możliwości użycia rekurencji, a w których funkcje są typem pierwszoklasowym, istnieje możliwość dodania obsługi rekurencji poprzez kombinator Y. Przykładem może być rachunek lambda.

Więcej informacji: pl.wikipedia.org