Invia.cz
Last minute
Tunisko
Dovolená v Chorvatsku
Pojeďte do Egypta
Bulharsko
Vydělávejte peníze s INVIA.CZ
Invia.cz
Last minute
Tunisko
Dovolená v Chorvatsku
Pojeďte do Egypta
Bulharsko
Vydělávejte peníze s INVIA.CZ
Rekurze znamená sebeopakování. Používá se velmi často v matematice a informatice.
Obsah |
V oblasti matematiky pojem rekurze chápeme jako definování objektu pomocí volání sebe sama. Využívá se například pro definici přirozených čísel, stromových struktur a některých funkcí.
V programování rekurze představuje opakované vnořené volání stejné funkce (podprogramu), v takovém případě se hovoří o rekurzivní funkci. Nedílnou součástí rekurzivní funkce musí být ukončující podmínka určující, kdy se má vnořování zastavit. Jelikož bývá nejčastějším zdrojem chyb, je třeba ji navrhnout dostatečně robustním způsobem a prověřit veškeré možné stavy.
Pro uplatnění rekurzivních algoritmů je zapotřebí, aby programovací jazyk umožňoval volání podprogramu ještě před ukončením jeho předchozího volání.
Po každém kroku volání sebe sama musí dojít ke zjednodušení problému. Pokud nenastane koncová situace, provede se rekurzivní krok.
Každý algoritmus využívající rekurzi lze přepsat do nerekurzivního tvaru při použití zásobníku nebo jiné paměťové struktury.
Rekurzivní chování může být různé v závislosti na tom, kolik podprogramů se jí účastní. Rozlišujeme dva základní typy dělení:
Druhé dělení:
Při kombinaci zmíněných typů rekurze lze docílit velmi komplikovaných struktur. Je třeba připomenout, že již z charakteru takovéhoto volání podprogramů nelze docílit jiné, než symetrické struktury.
Některé definice rekurze v sobě zahrnují prvky humoru a parodie na výkladové slovníky:
Tyto žerty v sobě však nesou poučení o nesprávném užívání rekurze a podávají jej poměrně zábavnou a srozumitelnou formou. Hlavním problémem předchozí ukázky je absence ukončující podmínky. Jak již bylo řečeno, ukončující podmínka je nedílnou součástí rekurze a její nesprávná formulace často vede na nekonečný cyklus (či cyklus nekonečný) a tím dochází k zhroucení programu.
Poněkud matoucí je i výklad rekurzivní zkratky. Například zkratka GNU v angličtině znamená „GNU's Not Unix“ (česky „GNU není Unix“), zkratka je tedy součástí definice významu samotné zkratky.
Díky rekurzi lze definovat nekonečnou strukturu objektů konečným popisem, nekonečné výpočty realizovat konečným zápisem rekurzivního programu.
V programování je rekurze využívána k definici rozsáhlých datových struktur. Vytvořený objekt obsahuje prvek stejného typu. Definujeme tak nekonečnou datovou strukturu konečným způsobem (například u dynamických struktur, kdy předem neznáme potřebnou velikost).
Rekurzivní definice bimárního stromu:
typedef struct { //definice typu uzel
unsigned int data;
uzel* levyPotomek; //potomek je také typu uzel
uzel* pravyPotomek;
} uzel
Dalším využitím je řešení obecných úloh rozkladem na dílčí úlohy stejného typu, které řešíme stejným způsobem. Tento způsob řešení je klíčem k návrhu mnoha důležitých algoritmů, proto je jednou ze základních částí dynamického programování. Často jej nalezneme pod označením „rozděl a panuj“, anglicky „divide and conquer“. Tato programovací technika je vhodná pouze pro omezený okruh úloh, u nichž je rozdělení na menší nezávislé úlohy stejného charakteru možné a přirozené. Pokud lze rekurzi takto využít, vede většinou ke krátkému a efektivnímu řešení problému.
Rekurze se velmi často využívá při syntaktické analýze textů formálních jazyků (programovací jazyky, matematické vzorce), například pomocí regulárních výrazů.
Typickým příkladem přirozeně rekurzivního algoritmu je průchod stromem:
void ProjdiStrom(uzel x) {
unsigned int i = 0;
while (i < x.count) {
ProjdiStrom(x.children[i]);
i++;
}
ZpracujUzel(x); // zde jsou prováděny operace s daty uloženými v daném uzlu
}
Pro zpracování celého stromu voláme na počátku proceduru s počátečním parametrem - kořenový uzel. Procedura rekurzivně volá sebe sama pro potomky aktuálního uzlu (tedy pro podstromy daného stromu), dokud nedosáhne k uzlům, které nemají žádné potomky (uzly bez potomků jsou nazývány „listy“).
Při vykonání určité operace se všemi soubory v adresářové struktuře na pevném disku je možné použít rekurzi, neboť na každý nalezený podadresář lze automaticky zavolat stejnou funkci.
Velmi zajímavou oblastí použití rekurze jsou fraktály.
Jednou ze základních součástí většiny programovacích jazyků jsou cykly. Jedná se o nejrozmanitější obměny syntaxe příkazů for, while a jim podobných. Cílem těchto nástrojů je umožnit programování opakovaných činností. Existují však i jazyky, které dokazují, že cykly nejsou jedinou cestou, a jejich užití buď nepodporují vůbec, či využívají těchto nástrojů pouze zřídka. Jedná se například o Lisp či Prolog. Pro řešení opakovaných činností používají právě rekurzi a suverénně dokazují, že v mnoha případech se jedná o mocnější a univerzálnější techniku.
Definice tohoto typu mají zpravidla dvě základní části. Počáteční tvrzení a způsob, jak z aktuálního stavu odvodíme stav následující.
Příkladem rekurzivní definice může být definice přirozených čísel:
Standardní způsob, jak definovat nové matematické či logické systémy je definovat objekty (typu “true” a “false”) a operace pro manipulaci s nimi. Veškeré platné výpočty v systému jsou pak definovány pravidly pro skládání těchto základních případů. Pokud dokážeme, že základní případy a pravidla jsou vypočítatelná, pak jakákoli rovnice v matematickém systému bude také vypočítatelná.
Může to znít nezajímavě, avšak tento druh důkazu je používán pro určení, zda výpočet je či není nemožný. Tím může často ušetřit hodně času. Například, tento druh důkazu byl použit pro dokázání, že obsah kruhu není jednoduchým poměrem jeho průměru, a že žádný úhel nemůže být roztrojen s kružítkem a pravítkem — obě hádanky fascinovaly staré národy.
Nejčastějším příkladem rekurzivní funkce je výpočet faktoriálu N!, který lze spočítat pro celá kladná čísla podle vztahu 
a pro N = 0 je N! = 1
faktoriál(N): pokud N = 0, potom výsledek = 1, jinak výsledek = N * faktoriál(N - 1)
Jelikož při každém průchodu funkcí snižujeme hodnotu čísla N a testujeme, zda již N nabylo hodnoty 0, má funkce konec.
Poznámka: V uvedeném příkladu je chyba, pokud je uvedená funkce volána pro číslo menší než nula, nebude nikdy splněna ukončující podmínka a dojde k zhroucení programu. Jedním z možných řešení je nahrazení podmínky N = 0 za N <= 0.
Pokud úloha má přímočaré nerekurzivní řešení, bývá rychlejší. Často však ztácí na přehlednosti. Vhodnou metodou může být například iterace:
faktoriál (N):
pokud N < 0, potom konec,
jinak
výsledek = 1,
pro i od 1 do N proveď
výsledek = výsledek * i,
konec
Jiným příkladem rekurzivního algoritmu může být úkol pro robota Karla, aby ušel polovinu vzdálenosti od místa, kde stojí, k protilehlé zdi, přestože neví, jak je zeď daleko. V takovém případě stačí vytvořit proceduru, během které v případě, že stojí již před zdí, tak se otočí čelem vzad, jinak udělá dva kroky, zavolá stejnou proceduru a udělá krok. (Předpokládejme, že před Karlem je sudý počet volných políček.)
DoPulky
znamena
kdyz bude zed
vlevo
vlevo
jinak
krok
krok
DoPulky
krok
konec
konec
Ukázkou vhodného užití rekurze je třídící algoritmus QuickSort. Jedná se jeden z nejrychlejších a zároveň i jednodušších algoritmů řazení. Princip spočívá v rozdělení posloupnosti čísel do dvou oblastí. Do jedné umístíme menší čísla než nějaká náhodně zvolená hodnota (nazýváme ji pivot) a do druhé větší. Při vhodném zvolení pivotu jsou obě oblasti přibližně stejně velké. V momentě, kdy jsou seřazeny obě části, je seřazená i celá posloupnost. Obě části se rekurzivně řadí stejným postupem, dokud nebudou mít jednotlivé úseky pouze jeden člen.
static void QuickSort(ref int[] array, long VLEVO, long VPRAVO){
int PIVOT = array[((VLEVO + VPRAVO)/2)];
long L = VLEVO;
long P = VPRAVO;
do {
while (array[L-1] < PIVOT) { L++;}
while (PIVOT < array[P-1]) { P--;}
if(L <= P){ // prohození čísel
int TMP = array[L-1];
array[L-1] = array[P-1];
array[P-1] = TMP;
L++;
P--;
}
}while(!(L > P));
if (VLEVO < P){ QuickSort(ref array, VLEVO, P); } // rekurzivní volání
if (L < VPRAVO){ QuickSort(ref array, L, VPRAVO); } // rekurzivní volání
}
Použití rekurze v algoritmech s sebou přináší výhody i nevýhody. Hlavní výhodou je jednoduchost a přehlednost algoritmu. Naopak hlavní nevýhodou je, že algoritmus pro velký počet vnoření obsadí poměrně velké množství paměti. Při každém vyvolání podprogramu je automaticky provedeno několik kroků. Uložení lokálních proměnných (proměnných používaných pouze pro potřeby aktuálně běžícího podprogramu) do zásobníku, předání parametrů a návratové adresy a skok do podprogramu. Po ukončení rekurze se díky uloženým návratovým adresám procházíme zpět stejnou cestou a uložené informace si opět vyzvedáváme.
Fibonacciho posloupnost je vhodnou ukázkou, jak lze řešit rekurzívní úlohu různými a různě efektivními způsoby.
Jedná se o posloupnost, jejíž první člen f(0) = 0, druhý člen f(1) = 1 a každý další člen je součet dvou předchozích. Prvních několik členů vypadá následovně:
n-tý člen posloupnosti lze nalézt pomocí rekurzivního algoritmu. Funkce se volá sama sebe pro výpočet dvou předchozích členů posloupnosti a ty následně sečte. Struktura volání podprogramů tvoří strom. Tento způsob výpočtu má exponenciální časovou složitost. Je to dáno tím, že při výpočtu vyšších čísel počítáme stále častěji prvky, které jsme již počítali.
fibonacci(N):
pokud N < 2, potom
pokud N < 1, potom výsledek = 0,
jinak výsledek = 1,
jinak
výsledek = fibonacci(N-1) + fibonacci(N-2)
n-té Fibonacciho číslo lze spočítat i bez rekurze. Stačí prvky posloupnosti počítat od začátku a ukládat je například do Pole (datová struktura). První dva členy jsou dány (0, 1) a každým součtem předchozích dvou prvků lze získát další prvek.
fibonacci(N):
P je pole[0 .. MaxN]
P[0] = 0;
P[1] = 1;
pro i od 2 do N proveď
P[i] = P[i-1] + P[i-2],
výsledek = P[N]
konec
Dokonce stačí ukládat si jen poslední dvě hodnoty a paměťovou složitost tak zredukovat na konstantní.