Tehnici de Programare

Defintii

Notiunea de recursivitate din programare este derivata in mod natural din notiunea de recusivitate din matematica, unde o notiune este definita recursiv daca in cadrul definitiei sale apare insasi notiunea ce se defineste.

Exemple:

-factorial

 1 daca n=0

n!=

n *(n-1)! daca n>0

In programare, instrumentul necesar si suficient pentru a exprima programe recursive este subprogramul pentru ca subprogramul da un nume unei actiuni care poate fi invocata prin numele respectiv.

Recursivitatea poate fi directa atunci cand in corpul subprogramului apare apelul acelui subprogram, sau indirecta daca apelul apare in corpul altui subprogram care se apleleaza din primul subprogram.

Autoapelul provoaca o noua activare a aceluiasi subprogram, ceea ce presupune executia instructiunilor subprogramului, incepand cu prima instructiune a acestuia si pana la autoapel, cand se activeaza din nou subprogramul s.a.m.d. Ca atare, partea de inceput a subprogramului se poate executa de o infinitate de ori. Pentru a se evita o asemenea situatie trebuie ca autoapelul subprogramului sa fie conditionat de indeplinirea unei anumite conditii. Daca conditia de autoapel (C) este indeplinita, atunci subprogramul este reactivat (reapelat), in caz contrar sirul de activari (apeluluri) ale subprogramului se intrerupe si se executa secventele ramase de executat din subprogram, activate in ordine inversa activarii.

Apelul unui subprogram recursiv, ca si al unuia nerecursiv presupune alocarea de memorie pe stiva a variabilelor locale, a parametrilor si a adresei de revenire. Ca atare pentru a nu se ajunge in situatia depasirii stivei se recomanda utilizarea unei solutii recursive numai daca numarul autoapelului (adancimea recursivitatii) nu este mare.

In cazul utilizarii recursivitatii se mai recomanda utilizarea variabilelor globale pentru a se evita crearea unor dubluri de variabile pe stiva.

Avantajul recursivitatii este acela ca:

- reduce lungimea textului sursa;

- conduce la solutii clare in comparatie cu solutiile iterative.

Recursivitatea se recomanda:

- in problemele ale caror solutii pot fi definite in termeni recursivi;

- in cazul problemelor complexe rezolvate prin backtracking.

Intotdeauna o problema recursiva are si o rezolvare iterativa si invers.

Utilizarea tehnicilor recursive nu conduce intotdeauna la solutii optime. Ca atare, se recomanda o analiza a eficientei solutiei recursive si a celei nerecursive si alegerea solutiei celei mai avantajoase