Rekurze (programování)

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

Rekurze v programování je situace, kdy je procedura nebo funkce vyvolána v rámci jednoho vlákna dříve, než je dokončeno její předchozí vyvolání. Rekurze může být přímá (procedura nebo funkce volá sebe samu), nebo nepřímá (procedura nebo funkce volá jiné procedury nebo funkce, ty mohou volat další, atd. až je v některé úrovni znovu vyvolána původní procedura nebo funkce).

Použití rekurze může usnadnit a zelegantnit řešení některých úloh.

Některé (zejména starší) programovací jazyky a některé kompilátory však rekurzi neumožňují; jiné vyžadují, aby programátor explicitně uvedl, že je daná procedura nebo funkce rekurzivní. Použití rekurze vede obvykle k jinému rozložení využití prostředků přidělených programu operačním systémem, případně k jejich rychlejšímu vyčerpání, proto se při programování obvykle snažíme rekurzi omezit, v krajním případě zcela odstranit.

Rekurzivní funkce[editovat | editovat zdroj]

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