Rekurzivní funkce (programování)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

V programování je rekurzivní funkce metoda, kdy jedna a tatáž funkce volá před svým dokončením sama sebe většinou 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.

Rekurzivní volání[editovat | editovat zdroj]

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

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

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