Rekurencja
Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) – odwoływanie się np. 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.
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 i 1. W przeciwnym wypadku nigdy 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, zawsze zwiększa ona zapotrzebowanie programu na pamięć operacyjną (chyba że zostanie użyta możliwa w pewnych przypadkach optymalizacja zwana rekurencją ogonową), gdyż wymaga 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. Jednak, niezaprzeczalną zaletą rekurencji jest przejrzystość programów, które z niej korzystają.
Jedną z typowych sytuacji, w których stosuje się rekurencję jest przeszukiwanie struktury danych w postaci nieregularnego drzewa, np. plików 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
- wielomiany Hermite'a
- wielomiany Legendre'a
- algorytm Euklidesa
- ciąg Fibonacciego
- definicja silni
- symbol Newtona
- cecha podzielności przez 3 dla liczby w zapisie dziesiętnym
Zobacz też
- rekursja pośrednia
- rekursja ogonowa (tail recursion)
- derekursywacja
- strategia typu dziel i zwyciężaj
- równanie rekurencyjne
- twierdzenie o rekurencji uniwersalnej
- efekt Droste
Linki zewnętrzne
- Thomas Bolander: Self-Reference. Stanford Encyclopedia of Philosophy, 2017-08-31. [dostęp 2018-01-17]. (ang.).