PC Laborator 10

Obiective

La sfârșitul acestui laborator studenții vor fi capabili:

• să înțeleagă funcționarea funcțiilor recursive;
• să implementeze și să apeleze funcții recursive;
• să folosească tool-ul de depanare GDB.

Funcții recursive

Un obiect se definește în mod recursiv dacă în cadrul definiției sale există o referire la el însuși.
Recursivitatea este un procedeu de programare în care o funcție se apelează pe ea însăși; o funcție care se auto-apelează poartă numele de funcție recursivă. O metodă de a înțelege mai ușor funcțiile recursive este imaginarea unui proces în execuție în care una dintre instrucțiuni este repetarea procesul în sine. O metodă și mai ușoară de a înțelege acest concept este compararea funcțiilor recursive cu papușile Matrioska, unde o păpușă conține în interiorul său una sau mai multe păpuși de același fel, excepție făcând ultima păpușă, cea mai mică dintre ele, care este goală.
Recursivitatea se folosește și în matematică - un exemplu ar fi șirul lui Fibonacci, care se folosește de ultimii doi termeni din șir pentru a afla termenul curent. Utilitatea recursivității, atât în matematică, cât și în cadrul programării, provine din posibilitatea de a defini un set infinit de termeni sau obiecte folosind o singură relație.
Recursivitatea diferă de structurile iterative, deși ambele concepte presupun execuția repetată a unei porțiuni de cod. În cadrul execuției unei funcții recursive se verifică o condiție a cărei nerealizare duce la o altă execuție a funcției, fără a termina execuția curentă care va fi suspendată. În momentul satisfacerii condiției se revine la execuția curentă, fiecare apel suspendat fiind reluat și încheiat, în ordine invers cronologică.

Atenție: Orice apel recursiv al unei funcții trebuie condiționat de o decizie care să împiedice apelarea funcției în buclă infinită.

Recursivitatea poate fi de două feluri:

• recursivitate directă (în care o funcție conține o referință către ea însăși);
• recursivitate indirectă (în care o funcție X conține o referință către o funcție Y, funcția Y conținând la rândul ei o referință către funcția X).
  

Exemplu de recursivitate directă

int factorial(int n){
    if(n<0){
        return 0;
    }else if(n==0){
        return 1;
    }
    int rez;
    rez = n*factorial(n-1);
    return rez;
}

Exemplu de recursivitate indirectă

int factorial(int n){
    if(n<0){
        return 0;
    }else if(n==0){
        return 1;
    }
    int rez;
    rez = inmul_fact(n, n-1);
    return rez;
}

int inmul_fact(int a, int b){
    int prod;
    prod = a*factorial(b);
    return prod;
}