Definícia

Rekurzia je častá technika zjednodušovania zložitejších problémov rozdelením pôvodného problému na podproblémy toho istého typu. Hovoríme, že objekt je rekurzívny, ak sa čiastočne skladá, alebo je definovaný pomocou seba samého.
Sila rekurzie spočíva v možnosti definovať nekonečnú množinu objektov konečným príkazom. Podobným spôsobom možno nekonečný počet výpočtov opísať pomocou konečného rekurzívneho programu. Hoci program nemusí obsahovať explicitné opakovania, rekurzívne algoritmy sú najvhodnejšie pri riešení výpočtov, kde je problém priamo definovaný rekurzívnym spôsobom.

^ TOP

Vlastnosti

Dôležitým prostriedkom na vyjadrenie rekurzie v programoch je procedúra (podprogram), ktorej identifikátor slúži na rekurzívnu aktiváciu jej tela. Ak procedúra volá sama seba, hovoríme o priamej rekurzii. Ak podprogram A volá podprogram B a ten zas volá podprogram A, hovoríme o nepriamej rekurzii. Použitie rekurzie nemusí teda byť okamžite zrejmé z textu programu.
Je zvykom združovať množinu lokálnych objektov (tj. lokálne premenné, konštanty, typy) s procedúrou. Každým rekurzívym volaním takejto procedúry vznikne nová množina jej lokálnych premenných. Tieto premenné majú síce tie isté identifikátory, aké mali pri predošlom volaní procedúry, ale ich hodnoty sú odlišné. Ku konfliktom neprichádza vďaka pravidlu viditeľnosti identifikátorov (vzťahujú sa vždy na ostatne vytvorenú množinu premenných).
Dôležitým prvkom v rekurzii je ukončovacia podmienka, ktorá zaručí, že počet vnorení nebude nekonečný.

^ TOP

Použitie

Rekurzívne riešenia problémov slúžia v prvom rade na pochopenie problému. V princípe je možné transformovať ľubovoľný rekurzívny algoritmus na iteratívny, ale stráca sa jeho prehľadnosť. Rekurzia však nemusí byť automaticky neefektívna. Príkladom je quicksort, alebo iné algoritmy operujúce na dynamických dátových štruktúrach.

^ TOP

Príklady

Prirodzené čísla

a) 1 je prirodzené číslo
b) nasledovníkom prirodzeného čísla je prirodzené číslo

Stromové štruktúry

a) k je strom (nazývaný prázdny strom)
b) ak l,m sú stromy, tak k s ľavým synom l a pravým synom m je tiež strom

Funkcia n-faktoriál n!

a) 0!=1
b) ak n>0, tak n!=n.(n-1)!

Fibonacciho postupnosť

a) f(0)=0
b) f(1)=1
c) f(n) = f(n - 1) + f(n - 2)

Fraktály

Fraktál je každé nekonečné vetvenie, ktoré zodpovedá určitému pravidlu. Je to jeden z prostriedkov súčasného modelovania, pričom platí, že po akomkoľvek zväčšení vyzerá obrázok úlne rovnako.