Rekurzivní funkce (programování)

Z Wikipedie, otevřené encyklopedie

V programování je rekurzivní funkce metoda, kdy jedna a tatáž funkce volá před svým dokončením sama sebe s použitím nové sady parametrů.

Příklad výpočtu faktoriálu čísla n. Protože faktoriál je definován takto

 n! = n * (n - 1) * (n - 2) * (n - 3) ... * 3 * 2 * 1 =  n * (n - 1)!

Funkce Faktorial používá při výpočtu rekurzivního algoritmu, který přesně odpovídá této definici

výpočet faktoriálu pomocí rekurzivního volání funkce

nfaktorial = Faktorial(n)

function Faktorial ( integer X )
   if X < 0 then return "Chybny argument" end if
   if X = 0 then return 1 end if
   return Faktorial(X-1) * X
end function

Použití rekurzivních funkcí může výrazně zjednodušit řešení úlohy. Má však různá úskalí, které je potřeba při implementaci rekurze vzít v úvahu. Každé volání rekurzivní funkce totiž zvyšuje hloubku zapouzdření funkce a vyžaduje zvláštní místo v paměti a čas procesoru. Nesprávné užití rekurze může způsobit obrovskou spotřebu paměti a velkou spotřebu času procesoru. V takovém případě je nutné se rekurzi vyhnout a nahradit ji jinou metodou - např. iterací.

výpočet faktoriálu pomocí iterace

function Faktorial (integer X)
     integer nfact
     if X < 0 then return "Chybny argument" end if
     nfact = 1
     for i = 1 to X do
           nfact = nfact * i
     end for
     return nfact
end function

V případě chybného použití rekurzivního volání může dojít k nekonečné smyčce. V případě, že funkce volá sama sebe se stále stejnými parametry, vzniká při každém dalším volání nová sada lokálních proměnných a funkce se zanořuje stále hlouběji a každé další volání požaduje stále další prostor v paměti pro vytvoření další sady proměnných a uložení návratové adresy. V okamžiku, kdy se vyčerpá veškerá volná paměť počítače, dojde k havárii programu.

Nevhodné může být použití rekurze i tehdy, když neúměrně zvýší složitost úlohy. Příkladem může být rekurzivní výpočet Fibonacciho posloupnosti, kde vede použití prosté rekurze k exponenciálně rostoucí složitosti výpočtu.

[editovat] Rekurzivní volání

Rekurzivní volání funkce je tedy takové volání, ke kterému dojde ve chvíli, kdy funkce samotná ještě nedokončila svou činnost. Volání může probíhat přímo nebo nepřímo.

přímé rekurzivní volání

function A(X)
{
    if (X < 1) return 1 end if
    return X + A(X/2)
}

nepřímé rekurzivní volání

function A(X)
{
   return 1 + B(X)
}
function B(X)
{
   return A(X-5) + C(X)
}

[editovat] Základní kroky při použití rekurzivní funkce

Každý program, který používá rekurzivní volání funkcí, by měl postupovat podle následujících základních kroků

1. inicializační algoritmus - rekurzivní funkce většinou potřebuje nějakou inicializační hodnotu, se kterou zahájí výpočet. To většinou zajišťuje jiná funkce, která není rekurzivní a která danou rekurzivní funkci volá a předává hodnotu, se kterou rekurzivní výpočet začíná
2. kontrola, zda vstupní parametr odpovídá stanoveným podmínkám. Pokud hodnota parametru odpovídá, rekurzivní funkce provede výpočet a vrátí hodnotu
3. rekurzivní funkce redefinuje řešení problému tak, že jej nějakým způsobem zmenší, zjednoduší nebo rozloží na dílčí podproblémy
4. volání funkcí, které řeší daný podproblém - tady nastává přímé nebo nepřímé volání sebe sama
5. sestavení výsledku
6. vrácení vypočtené hodnoty