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
lub inaczej:
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 poważnie 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;
}
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łady[edytuj | edytuj kod]
- algorytm Euklidesa
- cecha podzielności przez 3 dla liczby w zapisie dziesiętnym
- ciąg Fibonacciego
- definicja silni
- funkcja Ackermanna
- wielomiany Czebyszewa
- wielomiany Hermite’a
- wielomiany Legendre’a
- symbol Newtona
Zobacz też[edytuj | edytuj kod]
- derekursywacja
- strategia typu dziel i zwyciężaj
- efekt Droste
- funkcja rekurencyjna
- rekursja ogonowa (tail recursion)
- rekursja pośrednia
- równanie rekurencyjne
- twierdzenie o rekurencji uniwersalnej
Linki zewnętrzne[edytuj | edytuj kod]
- Eric W. Weisstein , Recursion, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12] (ang.).
- Thomas Bolander , Self-Reference, [w:] Stanford Encyclopedia of Philosophy [online], CSLI, Stanford University, 31 sierpnia 2017, ISSN 1095-5054 [dostęp 2018-01-17] (ang.). (Samoodniesienie)