rekurencja

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. Przykładem rekurencji jest obraz jaki powstaje, gdy postawimy przed sobą dwa lustra, lub gdy skierujemy kamerę na ekran, który wyświetla obraz z kamery, lub używając niektórych aplikacji do wideokonferencji, gdy udostępnia się pulpit i patrzy na swój udostępniony ekran wewnątrz okna tej aplikacji. Przykładem rekurencji jest także rosyjska zabawka Matrioszka. Społeczność hackerów stosuje często rekurencyjne nazwy dla wolnego oprogramowania. Niektóre strony w zabawny sposób pokazują czym jest rekurencja jak np. Google czy Słownik Hackerów (ang. Jargon File).