Sila rekurzie spočíva v možnosti definovať nekonečnú množinu objektov konečným príkazom. Rekurzívne algoritmy sú najvhodnejšie pri riešené problémov, pri výpočtoch funkcií alebo spracúvaní takých štruktúr údajov, ktoré už samé o sebe sú definované rekurzívnym spôsobom. Pomocou rekurzívnych procedúr (funkcií) sa dajú priamo riešiť problémy, pri rozklade ktorých na podproblémy vznikne čiastočný problém, ktorý je podobný pôvodnému, ale je v isto zmysle jednoduchší.

Pri procedúrach (funkciách) sa združujú aj jej lokálne objekty (premenné, konštanty), ktoré sú definované lokálne v rámci tejto procedúry a ktoré neexistujú, resp. nemajú zmysel mimo tieto procedúry. Každým rekurzívnym volaním 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é. Rovnaké pravidlo platí pre parametre procedúr (funkcií), ktoré sú zviazané s ňou. Rekurzívne procedúry (funkcie) dávajú možnosť nekonečných výpočtov. Preto je potrebné zaoberať sa otázkou ukončenia výpočtu. Základom je, aby sa rekurzívne volanie procedúry (funkcie) P riadilo podmienkou B, ktorá môže byť za určitých okolnosti neplnená.

procedúra P
začiatok
ak B tak (príkazy, P)
koniec

Jedným zo spôsobov, ako zaručiť ukončenie rekurzie, je použiť parameter, napr. n , procedúry P, ktorú potom voláme s n-1 , ako hodnotou parametra. Ukončenie rekurzívnych volaní je potom zaručené prostredníctvo podmienky n>0 namiesto podmienky B.

Rekurzívne volanie procedúry(funkcie) je také vyvolanie, ktoré nastáva ešte skôr ako predchádzajúce vyvolanie bolo dokončené. Rozlišujeme pritom dva druhy rekurzie a to priamu a nepriamu .

Priama rekurzia nastáva v tej procedúre (funkcií), ak sa v jej tele vyskytuje príkaz volania tejto procedúry(funkcie). V tomto prípade k rekurzívnemu vyvolaniu dôjde tým, že procedúra (funkcia) vyvolá samu seba.

Nepriama rekurzia nastáva vtedy, keď procedúra (funkcia) P vyvolá inú procedúru (funkciu) Q a behom vykonávania tejto procedúry sa znovu vyvolá procedúra (funkcia) P.

Každým vyvolaní rekurzívnej procedúry sa vyžaduje pridelenie určitého množstva pamäti potrebnej na lokálne premenné procedúry. Okrem týchto lokálnych premenných potrebujeme nejakú pamäť na uchovávanie momentálneho stavu výpočtu, v ktorom sa nachádza rekurzívna procedúra.

Rekurzívne algoritmy sú výhodné najmä vtedy, keď problém, ktorý sa rieši je definovaný rekurzívne. To však nezanemená, že rekurzívne definície zaručujú, že použitie rekurzívneho algoritmu bude najlepším spôsobom riešenia daného problému.

Programy ktorých sa neodporúča použiť rekurzia možno charakterizovať pomocou nasledujúcich schém:

procedúra P začiatok ak B tak (príkazy, P) koniec

procedúra P začiatok prikazy ak B tak p koniec

function FAKT1(n:integer):integer;
begin
if n>1 then FAKT1:=n*FAKT1(n-1)
else then FAKT1:=1;
end;

Nerekurzívne vieme túto funkciu prepísať pomocou cyklu:

function FAKT2(n:integer):integer;
var i, suc:integer ;
begin
suc:=1;
for i:=2 to n do suc:=suc*i;
faktorial:=suc;
end;

Ak tieto zápisy porovnáme z pamäťového hľadiska tak dostávame:

Pri vykonaní funkcie FAKT2 si v pamäti musíme pamätať tri premenné(parameter funkcie, i, suc). Keďže to nie je rekurzívna funkcia, tak počas celého vykonávania funkcie máme len tri premenné. Vo funkcií FAKT1 máme síce len jednu premenná a to parameter funkcie, ale pri niekoľko násobnom rekurzívnom zavolaní si musíme pamätať hodnotu premennej pri každom volaní.

Ak si to porovnáme pre hodnotu n=4, tak FAKT2 si pamätá len 3 premenné a FAKT1 má pri prvom zavolaní 1 premenná + rekurzívne volanie, druhú premennú pri prvom rekurzívnom vnorení a rekurzívne vnorenie a takto to pokračuje. Takže na konci vnárania máme 4 premenná, hodnotu funkcie na dne rekurzívneho vnárania a v pamäti uložené každé rekurzívne vnáranie. Z pamäťového hľadiska je rekurzívna funkcia faktoriálu neefektívna.

Ak si to porovnáme z časového hľadiska máme:

Funkcia FAKT2 sa vykonáva v cykle a v ňom je n-1 operácií, pred cyklom je operácia priradenia hodnoty a za ním je priradenie hodnoty funkcií. Spolu pri vykonávaní tejto procedúry je n+1 operácií. Funkcia FAKT1 sa rekurzívne vnára a pri parametri n, je to n vnorení a n vynorení, čo je spolu 2n operácií. Z časového hľadiska je nerekurzívny prepis faktoriálu efektívnejší.

Ukázali sme, že faktoriál pomocou rekurzívneho prepisu je neefektívny. Nie je to vo všetkých prípadoch tak. Sú problémy, ktoré by sme bez rekurzie alebo iných zložitých údajových štruktúr nevedeli naprogramovať. Napríklad iba jednoduchú úlohu z matematiky, akou je výpis všetkých permutácií bez opakovania, by sme bez rekurzie veľmi ťažko naprogramovali. Ak máme vypísať permutácie troch prvkov, tak je to ľahké, dáme tri do seba vnorení cykly, podmienku a vieme vypísať permutácie. Pri výpise permutácií zo štyroch prvkov vieme použiť štyri vnorené cyklu, ale čo ak číslo je ľubovoľné, napríklad 100. Tak už nastáva problém a rekurzívne riešenie je efektívnejšie ako prepis cez cykly.

Iným príkladom je Hilbertova krivka

Ak máme zadaný stupeň krivky, tak je to jednoduché. Pomocou príkazov sa dá nakresliť táto krivka, aj keď od tretieho stupňa počet príkazov exponenciálne pribúda. Čo ale ak stupeň vykreslenia nie je zvolený a ostáva na používateľovi aby si ho zvolil? Pri riešení tohto prípadu je nudné použiť rekurziu a dokonca rekurzívne riešenie je efektívnejšie ako nerekurzívne.

Rekurzia je silný nástroj na riešenie problémov. Je však potrebné rozlišovať situácie, kedy je rekurziu vhodné použiť a kedy nie.