Recursivitate

In informatica si in matematica,recursivitatea este un concept fundamental.

Recursivitatea s-a impus in programare, odata cu aparitia unor limbaje de nivel inalt, ce permit scrierea de module ce se autoapeleaza (PASCAL, LISP, ADA, ALGOL, C sunt limbaje recursive, spre deosebire de FORTRAN,BASIC,COBOL, nerecursive).

Recursivitatea e strans legata de iteratie.Iteratia este executia repetata a unei portiuni de program, pana la indeplinirea unei conditii (while, do-while , for din C).

Iteratia este uneori preferata din cauza vitezei mai mari si a memoriei mai reduse. Spre exemplu varianta recursiva a functiei Fibonacci duce la 15 apeluri pentru n=5, deci varianta iterativa este mult mai performanta. - -

Recursivitatea implica folosirea a cel putin unei stive. La fiecare apel recursiv sunt depuse in stiva date, care sunt extrase la revenirea din acel apel. E simplu daca datele pentru un apel se organizeaza intr-o structura, un apel insemnand introducerea in stiva a unei structuri, revenirea, extragerea structurii.

Se prezinta eliminarea recursivitatii pentru un program simplu, care citeste caracterele tastate pana la un blanc, tiparindu-le apoi in ordine inversa. -

Algoritmi de traversare si inversare a unei structuri

Algoritmi care implementeaza definitii recursive

Algoritmi de divizare

Algoritmi cu revenire (backtracking)

Traversarea si inversarea unei structuri inseamna efectuarea unor operatii oarecare asupra tuturor elementelor unei structuri in ordine directa, respectiv in ordine inversa. - Desi mai uzuale sunt variantele iterative, caz in care inversarea echivaleaza cu doua traversari directe (o salvare in stiva urmata de parcurgerea stivei), variantele recursive sunt mai elegante si mai concise. Se pot aplica structurilor de tip tablou, lista, fisier si pot fi o solutie pentru diverse probleme (transformarea unui intreg dintr-o baza in alta, etc). -

Programarea in limbajul C/C++ pentru liceu-Metode si tehnici de programare.Ed.Polirom 2005,Emanuela Cerchez,Marinel serban