Definiţie:
O funcţie recursivă este o funcţie care se apelează pe ea însăşi, direct sau indirect.
Recursivitatea poate fi directă – o funcţie P conţine o referinţă la ea însăşi, sau indirectă – o funcţie P
conţine o referinţă la o funcţie Q ce include o referinţă la P
Se pot deosebi două feluri de funcţii recursive:
Funcţii cu un singur apel recursiv, ca ultimă instrucţiune, care se pot rescrie uşor sub forma
nerecursivă (iterativă).
Funcţii cu unul sau mai multe apeluri recursive, a căror formă iterativă trebuie să folosească
o stivă pentru memorarea unor rezultate intermediare.
Recursivitatea este posibilă în C datorită faptului că, la fiecare apel al funcţiei, adresa de revenire,
variabilele locale şi argumentele formale sunt puse într-o stivă (gestionată de compilator), iar la
ieşirea din funcţie (prin return) se scot din stivă toate datele puse la intrarea în funcţie (se
“descarcă” stiva).
Apelul recursiv al unei funcţii trebuie să fie condiţionat de o decizie care să împiedice apelul în
cascadă (la infinit ); aceasta ar duce la o eroare de program – depăşirea stivei.
Orice funcţie recursivă trebuie să conţină cel puţin o instrucţiune if, plasată de
obicei chiar la început!
Prin această instrucţiune se verifică dacă mai este necesar un apel recursiv sau se
iese din funcţie.
Absenţa instrucţiunii if conduce la o recursivitate infinită (la un ciclu fără condiţie
de terminare)!
Pentru funcţiile de tip diferit de void apelul recursiv se face printr-o instrucţiune
return, prin care fiecare apel preia rezultatul apelului anterior!
Observaţii:
Funcţiile recursive nu conţin în general cicluri explicite (cu unele excepţii), iar repetarea
operaţiilor este obţinută prin apelul recursiv. O funcţie care conţine un singur apel recursiv ca
ultimă instrucţiune poate fi transformată într-o funcţie nerecursivă, înlocuind instrucţiunea if
cu while.
Fiecare apel recursiv are parametri diferiţi, sau măcar o parte din parametri se modifică de la
un apel la altul.
Se pune întrebarea: “Ce este mai indicat de utilizat: recursivitatea sau iteraţia?”
Algoritmii recursivi sunt potriviţi pentru a descrie probleme care utilizează formule recursive
sau pentru prelucrarea structurilor de date definite recursiv ( liste, arbori ), fiind mai eleganţi şi
mai simplu de înţeles şi verificat. Iteraţia este uneori preferată din cauza vitezei mai mari de
execuţie şi a memoriei necesare la execuţie mai reduse. Spre exemplu, varianta recursivă a
funcţiei Fibonacci duce la 15 apeluri pentru n=5, deci varianta iterativă este mult mai
performantă.
Apelul recursiv al unei funcţii face ca pentru toţi parametrii să se creeze copii locale apelului
curent (în stivă) , acestea fiind referite şi asupra lor făcându-se modificările în timpul execuţiei
curente a funcţiei. Când execuţia funcţiei se termină, copiile sunt extrase din stivă, astfel încât
modificările operate asupra parametrilor nu afectează parametrii efectivi de apel,
corespunzători. De asemenea, pentru toate variabilele locale se rezervă spaţiu la fiecare apel
recursiv.
Pe parcursul unui apel, sunt accesibile doar variabilele locale şi parametrii pentru apelul
respectiv, nu şi cele pentru apelurile anterioare, chiar dacă acestea poartă acelaşi nume!
De reţinut că, pentru fiecare apel recursiv al unei funcţii se crează copii locale ale parametrilor
valoare şi ale variabilelor locale, ceea ce poate duce la risipa de memorie.