Recursivitatea este frecvent folosita in prelucrarea structurilor de date definite recursiv. Un subprogram recursiv trebuie scris astfel incat sa respecte regulile :
a) Subprogramul trebuie sa poata fi executat cel putin o data fara a se autoapela ;
b)Subprogramul recursiv se va autoapela intr-un mod in are se tinde spre ajungerea in situatia de executie fara autoapel.Pentru a permite apelarea recursiva a subprogramelor, limbajul Pascal dispune de mecanime speciale de suspendare a executiei programului apelant, de salvare a informatiei necesare si de reactivare a programului suspendat .Pentru implementarea recursivitatii se foloseste o zona de memorie in care se poate face salvarea temporala a unor valori. La fiecare appel recursiv al unui subprogram se salveaza in aceasta zona de memorie starea curenta a executiei sale.Desi variabilele locale ale subprogramului apelant au aceleasi nume cu cele ale subprogramului apelat, orice referire la acesti identificatori se asociaza ultimului set de valori alocate in zona de memorie. Zona de memorie ramane alocata pe tot parcursul executie subprogramului apelat si se dealoca in momentul revenirii in programul apelat. Zona de memorie nu este gestionata explicit de programator ci de catre limbaj.La terminarea executiei subprogramului apelat recursiv, se reface contextul programului din care s-a facut apelul. Datorita faptului ca la fiecare autoapel se ocupa o zona de memorie, recursivitatea este eficienta numai daca numarul de autoapelari nu este prea mare pentru a nu se ajunge la umplerea zonei de memorie alocata.Recursivitatea ofera avantajunl unor solutii mai clare pentru probleme si a unei lungimi mai mici a programului. Ea prezinta insa dezavantajul unui timp mai mare de executie si a unui spatiu de memorie alocata ami mare. Este de preferat ca atunci cand programul recursiv poate fi transformat intr-unul iterativ sa se faca apel la cel din urma .