Recursivitate“Jocul pe care-l jucămeste să ne prefacemşi ne prefacemcă de fapt noi nu ne prefacem.Ne facemcă uităm cine suntem, şi apoi uitămcă noi am uitat. Cine suntem noi de fapt?”

Bernard Gunter

Ce este recursivitatea?

Un obiect sau un fenomen se defineşte în mod recursiv, dacă în definiţia sa există o referire la el însuşi.

În programare, recursivitatea este implementată cu ajutorul subprogramelor.

Când un subprogram este recursiv?

Un subprogram este recursiv dacă el se autoapelează (când subprogramul este lansat în execuţie, se fac apeluri la el însuşi).

Ce trebuie să urmărim atunci când construim o funcţie recursivă?

Trebuie să concepem o funcţie recursivă din două ramuri: - prima ramură a definiţiei recursive cuprinde una sau

mai multe definiţii directe (o valoare iniţială cunoscută)

Această parte din definiţiile recursive este esenţială şi face ca procesul de calcul să se oprească după un număr de paşi. Ea se numeşte condiţie de oprire sau terminare.

- a doua ramură a definiţiei recursive cuprinde descrierea operaţiilor care se fac la un pas oarecare al algoritmului.(formula de recurenţă)

Care sunt regulile pentru scrierea corectă a subprogramelor

recursive?

Orice subprogram recursiv trebuie să se execute, cel puţin o dată, fără a se autoapela. Condiţia de oprire se va scrie pentru valori extreme ale mulţimii valorilor de testat.

Autoapelurile trebuie să conducă spre situaţia (situaţiile) în care subprogramul se execută direct (fără autoapel).

Execuţia programelor recursive

La activarea unui subprogram, se salvează în stiva procesorului (stack): valorile parametrilor transmişi prin valoare şi

adresele parametrilor transmişi prin adresă; valorile variabilelor locale în subprogram; adresa de revenire din subprogram.

Execuţia programelor recursive

În cazul subprogramelor recursive mecanismul este, bineînţeles, acelaşi. La fiecare apel al subprogramului, se va aloca în stivă un nou nivel unde se va salva setul de valori (parametri, variabile locale, adresa de revenire) corespunzătoare stării curente a execuţiei subprogramului.

De subliniat faptul că, deşi parametrii şi variabilele locale au, pentru toate apelurile, aceeaşi identificatori, valorile lor diferă de la o execuţie la alta. În referirile la identificatori, valorile acestora corespund întotdeauna ultimului set de valori salvate.

La terminarea execuţiei unui apel recursiv, se reia ultima execuţie întreruptă, în stivă fiind activ setul de valori corespunzătoare acesteia.

Concluzie

Ideea de bază a recursivităţii este aceea că fiecare nou autoapel al funcţiei (autogenerarea unui nou proces de acelaşi fel) ne apropie de soluţia finală, care corespunde valorii iniţiale cunoscute.