Rekurzia

Čo je to podprogram?

Koncept podprogramu je jednoduchý: je to skupina príkazov, ktorej dáme nejaké meno a neskôr ju podľa tohto mena voláme.

Celé to teda vyzerá tak, že niekde definujeme podprogram a v inej časti programu ho potom zavoláme. Keď sa program dostane na toto miesto, vykoná všetky príkazy podprogramu a potom pokračuje z miesta, kde bol podprogram zavolaný. Počítač si teda (aspoň pri väčšine programovacích jazykov) vždy uchováva informáciu o tom, odkiaľ bol podprogram zavolaný, aby sa tam po jeho dokončení mohol vrátiť.

Toto vyzerá ako úplná zbytočnosť - radšej sme mohli príkazy z podprogramu napísať na miesto, odkiaľ sme ho chceli volať. Výhodou podprogramu ale je, že ho môžeme zavolať aj viackrát, z rôznych miest programu. To znamená, že ak vieme, že nejaký zložitejší úkon budeme musieť robiť na rôznych miestach programu, môžeme si na to napísať podprogram, čím si ušetríme kopec písania a znížime tým aj šancu, že sa pri písaní pomýlime.

Jazykové okienko

Existujú rôzne slová označujúce podprogramy, každé má trochu iný význam:

1. procedúra je najjednoduchší druh podprogramu: Je to jednoducho zhluk príkazov, ktoré sa vykonajú.

2. funkcia je termín prebraný z matematiky. Ide o podprogram, ktorý má na základe nejakých vstupných údajov vypočítať nejaký výstup. V niektorých programovacích jazykoch (napr. Haskell) sa trvá na tom, aby funkcia nerobila nič iné, teda aby nemala žiadne vedľajšie účinky (teda aby sa naozaj správala ako funkcia v matematike). Iné programovacie jazyky (napr. C++) sú v tomto ohľade menej striktné a povoľujú, aby funkcia robila aj veci ovplyvňujúce zvyšok programu. Tým pádom v nich nie je potrebné zvlášť definovať procedúry, keďže namiesto procedúry môžeme použiť napr. funkciu, ktorá vždy vráti výsledok nula. Preto sa slovom funkcia občas myslí aj podprogram všeobecne.

3. Niekedy sa možno stretnete aj s termínom metóda. Toto slovo sa používa v objektovo orientovanom programovaní a neznamená nič iné, ako funkciu, alebo procedúru, ktorá existuje v kontexte nejakého objektu (ak ste tomuto nerozumeli, nevadí, zatiaľ to ani nepotrebujete).

V tomto texte budem ďalej namiesto slova podprogram používať slovo funkcia.

Keď už hovoríme o pojmoch, tak si definujme ešte jeden:

• Postupnosti príkazov, ktoré funkciu tvoria, sa zvykne hovoriť aj telo funkcie.

Volanie funkcie vo funkcii, alebo we need to go deeper

Volanie funkcie nie je obmedzené iba na hlavný program. Vnútri tela funkcie môžeme volať iné funkcie. Vnútri iných funkcií potom môžeme volať ďalšie atď. Vyzerá to asi takto:

Pri každom volaní funkcie si počítač zapamätá, odkiaľ bola zavolaná. Túto informáciu si uchováva, až kým sa nevykoná celé telo danej funkcie. Vtedy program túto informáciu využije (aby vedel, kde má pokračovať) a následne ju už môže zabudnúť. To znamená, že keď vnútri jednej funkcie zavoláme druhú funkciu, počítač si musí zároveň pamätať, odkiaľ bola zavolaná prvá funkcia aj odkiaľ bola zavolaná druhá funkcia. Pre príklad na obrázku to znamená, že keď sa funkcia2 vykonávala prvý krát, počítač si musel pamätať miesta, z ktorých boli zavolané funkcia2, funkcia1, aj funkcia0. Keď bola funkcia2 volaná druhý raz, už si nemusel pamätať, odkiaľ bola volaná funkcia1, keďže táto funkcia medzičasom skončila. Keď bola funkcia2 zavolaná tretí raz, už si nemusel pamätať ani to, odkiaľ bola volaná funkcia0.

Nekonečná rekurzia

Čo by sa stalo, keby sme vnútri tela funkcie zavolali tú istú funkciu? Po prvom zavolaní funkcie v hlavnom programe by sa začali vykonávať jej príkazy, až po kým by funkcia nezavolala sama seba. V tom okamihu by sa znovu od začiatku začali vykonávať príkazy danej funkcie, až kým by znovu nezavolala sama seba. A takto by to išlo ďalej a ďalej.

Technika, kde funkcia volá sama seba, sa nazýva rekurzia. V praktickom programovaní vznikajú pri nekonečnej rekurzii isté technické problémy (Konkrétne, pri každom zavolaní funkcie si počítač musí zapamätať, odkiaľ bola zavolaná, pričom túto informáciu môže zabudnúť, až keď sa funkcia úplne vykoná (čo nenastane nikdy). To znamená, že po nejakom počte zavolaní sa mu zaplní celá časť pamäte, ktorú mal na tento účel vyhradenú.), preto je v mnohých jazykoch nepoužiteľná.

Chvostová rekurzia

Rekurzia nemusí byť nutne nekonečná. Ak funkcia vo svojom tele volá sama seba len ak sú splnené určité podmienky, pričom tieto podmienky po nejakom počte zavolaní prestanú platiť, funkcia sa zavolá iba konečný počet krát. Po poslednom zavolaní funkcie sa funkcia vykoná (bez toho, aby sa zavolala znovu), následne sa dokončí vykonávanie predošlého volania (vykonajú sa príkazy nachádzajúce sa za volaním funkcie), potom sa dokončí predošlé volanie atď., až kým sa nedostaneme k miestu, kde bola funkcia zavolaná na začiatku.

Všeobecná rekurzia

Nie sme obmedzení na to, aby sa funkcia vo svojom tele volala iba raz, pokojne sa môže zavolať aj viackrát. Alebo môže volať nejakú inú funkciu, ktorá potom naspäť zavolá ju. Kreativite sa medze nekladú.