Recursivitatea

Recursivitate

Obiective:

Studiind această temă veţi deveni capabili:

- să definiţi noţiuni recursive;

- să explicaţi realizarea recursivităţii în programare;

- să explicaţi mecanismul recursivitţii;

- să definiţi proceduri recursive;

- să definiţi funcţii recursive;

- să realizaţi algoritmi recursive;

- să explicaţi avantajele recursivităţii;

- să explicaţi dezavantajele recursivităţii;

- să explicaţi relaţia ‘ciclu - recursie’;

Recursivitatea reprezintă o tehnică de programare de o importanţă deosebită. Ea permite o exprimare extrem de concisă şi clară a algoritmilor de rezolvare a unor probleme complexe. În matematică, o noţiune este definită recursiv dacă în cadrul definiţiei apare noţiunea care se defineşte. De exemplu, definiţia recursivă a factorialului unui număr natural n este:

1, dacă n=0

n! =

n*(n-1)!, dacă n>0

5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 120

Se observă tendinţa de identificare a unor valori direct calculabile, urmată de utilizarea lor în vederea obţinerii valorii căutate.

Astfel, o definiţie recursivă trebuie să satisfacă următoarea condiţie: valoarea funcţiei trebuie să fie ori direct calculabilă, ori calculabilă cu ajutorul unei valori direct calculabile. Această condiţie se numeşte condiţie de consistenţă. Un exemplu de condiţie inconsistentă este următoarea:

1, dacă n=0

n! =

n*(n+1)!, dacă n>0

În programare, recursivitatea se exprimă cu ajutorul subprogramelor deoarece ele se identificş printr-un nume care este apoi specificat apoi în apeluri.

Un subprogram este recursiv dacă se autoapelează. Dacă apelul subprogramului apare chiar în corpul său, recursivitatea se numeşte directă. Iar dacă apelul subprogramului recursiv apare în corpul unui alt subprogram care se apelează direct sau indirect din subprogramul recursiv, recursivitatea se numeşte indirectă.

Fiecare apel de subprogram crează un cadru activ. În acest cadru se salvează adresa de revenire din subprogram, sunt alocate variabilele locale, parametrii formali transmişi prin valoare şi sunt instalate corespondenţele respective dintre parametrii formali transmişi prin valoare şi parametrii actuali.

Un subprogram este activ de la apelul său până la revinirea în subprogramul apelant. Subprogramul rămîne activ, chiar dacă din cadrul său se activează alte subprograme. Astfel, se poate spune, că un subprogram este recursiv dacă apelul său apare când subprogramul este activ.

Executarea unei proceduri nerecursive P1 care apelează o altă procedură nerecursivă P2 constă în:

- executarea secvenţei de început a procedurii P1 care precede apelul procedurii P2;

- executarea procedurii P2:

- executarea secvenţei de sfârşit a procedurii P1.

Dacă procedura P1 este recursivă direct, în locul apelului P2 va apărea autoapelul P1. Apelul procedurii P1 determină o primă activare a procedurii, care cuprinde executarea secvenţei de început, după care autoapelul P1 determină o nouă activare a procedurii P1 în cadrul căreia se execută secvenţa de început şi autoapelul P1 care determină a treia activare ş.a.m.d.

Executarea procedurii recursive P1 va determina activări repetate ale procedurii P1 în cadrul căreia se execută secvenţa de început a procedurii şi autoapelul. Fiecare activare presupune crearea cadrului activ. Pentru a respecta proprietatea de finititudine a algoritmului este obligatoriu ca autoapelul procedurii P1 să fie legat de îndeplinirea unei anumite condiţii.