V oblasti programovania existuje mnoho spôsobov, ako vytvárať zložité vzory a riešiť problémy, či už ide o vizuálnu reprezentáciu alebo komplexné algoritmy. Dve základné metódy, ktoré sa na to využívajú, sú cykly a rekurzia. Zatiaľ čo cykly opakujú výpočet sekvenčne, rekurzia prináša iný prístup, kde sa funkcia odvoláva sama na seba, čo umožňuje elegantné riešenia pre problémy, ktoré možno rozdeliť na menšie, podobné podproblémy.
Kreslenie Stromčeka z Hviezdičiek v C Programovaní
Kreslenie textových vzorov v konzole je častým úvodným cvičením v programovaní. Pre vytvorenie „stromčeka z hviezdičiek“ v jazyku C sa zvyčajne používajú cykly na riadenie počtu medzier a hviezdičiek v každom riadku.
Základom je pochopiť vzor: každý riadok stromčeka má najprv určitý počet medzier (pre centrovanie) a potom nepárny počet hviezdičiek, ktorý sa s každým riadkom zvyšuje. Kmeň stromčeka je potom reprezentovaný jednou alebo viacerými hviezdičkami v strede.
Pre implementáciu v C by sa mohol použiť vnorený for cyklus: vonkajší cyklus by iteroval cez riadky stromčeka (určujúc jeho výšku), a vnútorné cykly by vypisovali najprv medzery a následne hviezdičky. Tento prístup demonštruje použitie základných riadiacich štruktúr jazyka C na generovanie vizuálnych výstupov v textovom režime.
Základy Rekurzie v Programovaní
Opakovanie výpočtov v programovaní je možné pomocou cyklov, ako sú for-cyklus alebo while-cyklus. Rekurzia predstavuje ďalší spôsob, kde sa výpočet opakuje prostredníctvom volaní podprogramu, teda funkcie volajúcej samú seba.
Rekurzia sa často využíva pri riešení problémov, ktoré možno rozložiť na menšie časti. Niektoré z týchto menších častí sú potom riešené opätovným volaním tej istej funkcie. Keďže toto druhé (tzv. rekurzívne) volanie rieši menšiu úlohu než pôvodná, zvyšuje sa pravdepodobnosť, že riešenie sa priblíži k očakávanému výsledku. Rekurzia v programovaní teda znamená, že funkcia najčastejšie zavolá samú seba, t.j. že funkcia je definovaná pomocou samej seba.
Hĺbka Rekurzie a Zásobník Volaní
Pri každom volaní funkcie, či už rekurzívnej alebo nie, operačný systém si niekde zapamätá nielen návratovú adresu, aby po skončení funkcie vedel, kam sa má vrátiť, ale aj menný priestor tejto funkcie. Niektoré jazyky, ako napríklad Python, majú na tieto účely rezervu, napríklad okolo 1000 vnorených volaní. Prekročenie tejto hĺbky môže viesť k pádu programu (tzv.
Ukončenie Rekurzie - Triviálny Prípad
Aby sme nevytvárali nikdy nekončiace programy, t.j. nekonečnú rekurziu (ktorá aj tak veľmi rýchlo spadne), niekde do tela rekurzívnej funkcie musíme vložiť test, ktorý zabezpečí, že rekurzia predsa len skončí. Keďže rekurzia vlastne slúži na opakovanie výpočtu, budeme musieť nastaviť, kedy (v akých prípadoch) toto opakovanie, teda rekurzívne volanie, končí. Na začiatok funkcie umiestnime podmienený príkaz if, ktorý otestuje, či už nenastal taký prípad, že netreba opakovať výpočet aj s rekurzívnym volaním.
V tomto prípade by možno stačilo vykonať len nejaké „nerekurzívne“ príkazy a skončiť. Takýto špeciálny prípad, keď už nebude potrebné rekurzívne volanie, budeme volať triviálnym prípadom (base case). Môžeme si to predstaviť aj takto: rekurzívna funkcia rieši nejaký komplexný problém a pri jeho riešení volá samu seba (rekurzívne volanie, recursive case) väčšinou s nejakými pozmenenými údajmi. V niektorých prípadoch ale rekurzívne volanie na riešenie problému nepotrebujeme, ale vieme to vyriešiť „triviálne“ aj bez nej (riešenie takejto úlohy je už „triviálne“).
Akciou triviálneho prípadu môže byť napríklad príkaz pass (príkaz označuje nerob nič), čo znamená, že sa zabudnú všetky lokálne premenné na tejto úrovni.
Typy Rekurzie
Chvostová Rekurzia
Rekurzii, v ktorej za rekurzívnym volaním nie sú ďalšie príkazy, hovoríme chvostová rekurzia. Najčastejšie jediné rekurzívne volanie je posledným príkazom funkcie. Zrejme by ju bolo veľmi jednoduché prepísať bez použitia rekurzie, napríklad pomocou while-cyklu (alebo for-cyklu). Po experimentovaní s výmenou riadkov, ako je vypisovanie a rekurzívne volanie, je vidieť, že aj takúto rekurzívnu funkciu možno prepísať len pomocou cyklu.
Pravá Rekurzia
Rekurzie, ktoré už nie sú obyčajné chvostové, sú na pochopenie trochu zložitejšie. Nejaké príkazy sú pred aj za rekurzívnym volaním. Aj v ďalších príkladoch môžete vidieť pravú rekurziu. Keď ako triviálny prípad pridáme výpis hviezdičiek, toto sa vypíše niekde medzi postupnosť čísel.
Aplikácia Rekurzie v Informatike
Rozdeľuj a Panuj
Pri rozmýšľaní nad rekurzívnym riešením problému je veľmi dôležité správne rozdeliť veľký problém na jeden alebo aj viac menších, tie rekurzívne vyriešiť a potom to správne spojiť do jedného výsledku. Informatici tomu hovoria rozdeľuj a panuj (divide and conquer). Pri takomto rozhodovaní funguje matematická intuícia a tiež nemalá programátorská skúsenosť.
Matematické Funkcie
Faktoriál
V nasledujúcom príklade počítame
Ostatné prípady sú už rekurzívne: na to, aby sme vyriešili zložitejší problém (n faktoriál), najprv vypočítame jednoduchší ((n-1) faktoriál) - zrejme pomocou rekurzie - a z neho skombinujeme (násobením) požadovaný výsledok. Hoci toto riešenie nie je chvostová rekurzia (po rekurzívnom volaní faktorial sa musí ešte násobiť), vieme ho jednoducho prepísať pomocou cyklu. Zdá sa, že tento algoritmus už nemá problém s obmedzením na hĺbku vnorenia rekurzie.
Binomické Koeficienty a Pascalov Trojuholník
Ďalší príklad ilustruje využitie rekurzie pri výpočte
Každý prvok v tomto trojuholníku zodpovedá bin(n, k), kde n je riadok tabuľky a k je stĺpec. Teda každé číslo je súčtom dvoch čísel v riadku nad sebou, pričom na kraji tabuľky sú 1.
Fibonacciho Postupnosť
Na podobnom princípe, ako napríklad výpočet faktoriálu, funguje aj
Grafické Kreslenie Pomocou Rekurzie
Rekurziu môžeme používať nielen pri výpočtoch, ale napríklad aj pri kreslení pomocou korytnačky (turtle graphics). V nasledujúcej ukážke môžete vidieť, že rekurzívna špirála sa kreslí tak, že sa najprv nakreslí úsečka dĺžky d, korytnačka sa otočí o 60 stupňov vľavo a dokreslí sa špirála s väčšími hodnotami. Toto celé skončí vtedy, keby sme chceli nakresliť špirálu väčšiu ako 100 - takáto špirála sa už nenakreslí.
Binárne Stromy
Medzi informatikmi sú veľmi populárne
- strom(n - 1) # nakresli ľavý podstrom (n-1).
- strom(n - 1) # nakresli pravý podstrom (n-1).
Binárne stromy môžeme rôzne vylepšovať, napríklad vetvy stromu sa vo vyšších úrovniach môžu rôzne skracovať, uhol o ktorý je natočený ľavý a pravý podstrom môže byť tiež rôzny. Algoritmus binárneho stromu môžeme zapísať aj bez parametra n, ktorý určuje úroveň stromu. V tomto riešení si všimnite, kde sme zmenili hrúbku pera, aby sa strom kreslil rôzne hrubý v rôznych úrovniach. Tiež sa tu na posledných „konároch“ nakreslili zelené listy - pridali sme ich v triviálnom prípade. Každé spustenie tohto programu nakreslí trochu iný strom.
V nasledujúcom riešení vzniká zaujímavý efekt tým, že v triviálnom prípade urobí korytnačka malý úkrok vpravo a teda sa nevracia po tých istých čiarach a preto sa ani nevráti presne na to isté miesto, kde štartovala kresliť (pod)strom. Binárny strom sa dá nakresliť viacerými spôsobmi aj nerekurzívne. V jednom z nich využijeme zoznam korytnačiek, pričom každá z nich po nakreslení jednej úsečky „narodí“ na svojej pozícii ďalšiu korytnačku (vytvorí svoju kópiu), pričom ju ešte trochu otočí. Pre korytnačky na poslednej úrovni sa už ďalšie nevytvárajú, ale na ich koncoch sa nakreslí zelená bodka. Program na záver vypíše celkový počet korytnačiek, ktoré sa takto vyrobili (je ich presne toľko, koľko je zelených bodiek ako listov stromu). Všimnite si pomocnú funkciu nova(), ktorá vytvorí novú korytnačku a nastaví jej novú pozíciu aj smer natočenia. Funkcia ako výsledok vráti túto novovytvorenú korytnačku.
Pochopenie rekurzie pomocou stromov | Stromy a rekurzia | Rekurzívne dátové štruktúry | Geekific
Fraktály
Zaujímavé je to, že niektoré rekurzívne krivky sa dajú nakresliť aj jedným ťahom (po každej čiare sa prejde len raz). Špeciálnou skupinou rekurzívnych kriviek sú
Začneme veľmi jednoduchou, tzv.
Ďalšie Príklady Rekurzívnych Úloh
Medzi ďalšie typické rekurzívne úlohy patria: konverzia čísla na reťazec a naopak (napríklad funkcie tostr(cislo) a toint(retazec)), počítanie výskytov znaku v reťazci (funkcia pocet(znak, retazec)), nájdenie minima a maxima v zozname (funkcia min_max(zoznam)), výpočet najväčšieho spoločného deliteľa (NSD), súčet prvkov zoznamu (funkcia sucet(zoznam)), overenie, či je reťazec palindróm (funkcia palindrom(retazec)), a súčet kladných/záporných prvkov zoznamu (funkcia dva_sucty(zoznam)).
Pre grafické aplikácie sú bežné aj úlohy ako kreslenie farebných bodiek na koncoch všetkých vetvičiek binárnych stromov, vyfarbovanie trojuholníkov v rôznych úrovniach vnorenia, alebo kreslenie fraktálnych vzorov ako krížiky a pyramídy s rôznymi úrovňami zložitosti (napríklad funkcie ako vpisane3(n, a), vpisane4(n, a), kriziky4(n, a), kriziky(n, a, pocet), pyramida(n, a), pyramida3(n, a) a troj3(n, a)).