Rekurencja

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

Przykład rekurencji w sztuce użytkowej (efekt Droste)

Trójkąt Sierpińskiego

Efekt nieskończonego lustra

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).

Przykłady

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:

1. mój ojciec jest starszy ode mnie
2. mój ojciec jest czyimś synem
3. ojciec mojego ojca jest starszy od mojego ojca
4. ojciec mojego ojca jest czyimś synem
5. itd.

Na przykładzie zastosowań matematycznych poniższa definicja ciągu Fibonacciego jest rekurencyjna:

$\mathrm {fib} (0)=0$

$\mathrm {fib} (1)=1$

$\mathrm {fib} (n)=\mathrm {fib} (n-1)+\mathrm {fib} (n-2)$   dla  $n\geqslant 2,$

lub inaczej:

${\text{fib}}(n)={\begin{cases}0&{\text{dla }}n=0\\1&{\text{dla }}n=1\\{\text{fib}}(n-1)+{\text{fib}}(n-2)&{\text{dla }}n>1.\end{cases}}$

gdyż definiuje funkcję odwołując się w definicji do niej samej.

Każda definicja rekurencyjna potrzebuje przynajmniej jednego przypadku bazowego (nierekurencyjnego); w tym przypadku są to wartości dla 0 i 1. W przeciwnym wypadku nigdy się nie zakończy.

Dla przykładu, obliczenie $\mathrm {fib} (4)$ wygląda następująco:

$\mathrm {fib} (4)=\mathrm {fib} (3)+\mathrm {fib} (2)=(\mathrm {fib} (2)+\mathrm {fib} (1))+(\mathrm {fib} (1)+\mathrm {fib} (0))$${}=((\mathrm {fib} (1)+\mathrm {fib} (0))+\mathrm {fib} (1))+(\mathrm {fib} (1)+\mathrm {fib} (0))=((1+0)+1)+(1+0)=3$

Innym przykładem jest wyliczanie największego wspólnego dzielnika za pomocą algorytmu Euklidesa:

1. $\operatorname {gcd} (0,n)=n$
2. $\operatorname {gcd} (k,n)=\operatorname {gcd} (n\ {\text{mod }}k,k)$ dla $k>0$     $(n\ {\text{mod }}k$ oznacza tu resztę z dzielenia $n$ przez $k).$

lub inaczej:

${\text{gcd}}(k,n)={\begin{cases}n&{\text{dla }}k=0;\\{\text{gcd}}(n{\text{ mod }}k,k)&{\text{dla }}k>0.\end{cases}}$

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 $\mathrm {fib} (4)$ niepotrzebnie jest dwukrotnie obliczana wartość $\mathrm {fib} (2)$ (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;
    }

Inne przykłady

• 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ż

• derekursywacja
• strategia typu dziel i zwyciężaj
• efekt Droste
• funkcja rekurencyjna
• rekurencja pośrednia
• równanie rekurencyjne
• twierdzenie o rekurencji uniwersalnej

Linki zewnętrzne

• Rekurencja (ang.) w encyklopedii MathWorld
• ThomasT. Bolander ThomasT., Self-Reference, [w:] Stanford Encyclopedia of Philosophy, CSLI, Stanford University, 31 sierpnia 2017, ISSN 1095-5054 [dostęp 2018-01-17]  (ang.).