Rekurzia je opakovanie. Rekurzívny podprogram je taký podprogram, ktorý volá sám seba. Ak do rekurzívneho podprogramu neuvedieme podmienku ukončenia, bude sa opakovať donekonečna, hovoríme o nekonečnej rekurzii. Rekurzívny podprogram s podmienkou ukončenia využíva konečnú rekurziu.

  • Rekurzia je mocný nástroj ale programátor musí zabezpečiť, aby niekde počas programu došlo k naplneniu ukončovacej podmienky.
  • Každý rekruzívny algoritmus je možné prepísať na jeho iteračnú formu (čiže pomocou for alebo while).

Kedy používať rekurziu:

  • Rekurzívny program je vhodný, ak riešený problém alebo používané údaje sú definované rekurzívne.
  • Pri zložitejších rekurzívnych schémach je však transformácia na iteratívny tvar veľmi nepraktická.
  • Programy, ktoré sú svojou podstatou rekurzívne (skôr než iteratívne), majú byť implementované pomocou rekurzívnych funkcií.

Mechanizmus fungovania rekurzie v jazyku C je pomerne zložitý na pochopenie (zatiaľ) ale jej použitie si vieme veľmi ľahko vysvetliť na príklade, ktorý v rámci cvičenia riešime. Kto má záujem môže si pozrieť video v spodnej časti stránky.

Pr. Karol má zdvojnásobiť počet značiek. Teda ak stojí napr. na dvoch značkách navýši ich počet na 4. Toto je pomerne zložitá úloha ak sú zakázané premenné. Tento problém sa dá elegantne vyriešiť rekurzívnym programovaním. 

Riešenie:

Algoritmus v textovej podobe

Vývojový diagram algoritmu

Implementácia algoritmu v jazyku C

Najprv pre zamýšľanú funkciu multiply() navrhneme algoritmus v textovej podobe

  1. Je potrebné overiť či Karol stojí na značke. 
    1. Ak áno → značku zodvihne → následne funkcia zavolá samú seba. Vidíme, že k bodu 2. sa vykonávanie funkcie nedostalo. Ale značka je zodvihnutá, teda v nasledovnom kroku bude o jednu značku pod Karolom menej. V istom momente Karol zodvihne aj poslednú značku.
    2. Ak nie → koniec funkcie (nie je čo zobrať). Ukončenie funkcie znamená, že vo funkcii, ktorá volala túto ukončujúcu sa funkciu sa môže program posunúť na ďalší riadok (bod 2).
  2. Potom je potrebné položiť zodvihnutú značku a k nej pridať jednu navyše.



void multiply()
{  
    if(beepers_present()) 
    {
        pick_beeper();   
        multiply(); // rekurzívne volanie!!
       			    // ďalšie kroky sa vykonajú až 
					// keď funkcia multiply() skončí
        put_beeper();
        put_beeper();
    }
}