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;
}

Tool-ul de depanare GDB

Depanatorul GNU, cunoscut drept GDB (GNU debugger), este depanatorul standard pentru sistemul de software GNU.
Scopul unui depanator precum GDB este de a permite utilizatorului să vadă ce se întâmplă în interiorul unui alt program în timp ce acesta se execută sau ce s-a întâmplat cu programul în momentul în care acesta a dat crash.
GDB este capabil de a face 4 mari categorii de operații (și alte tipuri de operații ce duc la îndeplinirea celor 4):

• să pornească programul, specificând orice ar putea interveni în buna funcționare a acestuia;
• să facă programul să se oprească din execuție în anumite condiții specificate de utilizator;
• să examineze ce s-a întâmplat în momentul opririi programului;
• să schimbe anumite lucruri în program pentru a putea corecta efectele unui bug și a investiga urmările altuia.
  

Odată pornit, GDB citește comenzi din terminal până la întâlnirea comenzii de ieșire "quit".

Atenție: Pentru a putea folosi debugger-ul, la generarea fișierului executabil trebuie folosită opțiunea -g, care adaugă simboluri de debug în executabil, fără de care depanarea nu este posibilă. (vezi Laboratorul 1)

Exemplul unei comenzi de compilare în vederea depanării:

  student@pracsis01 ~/Desktop $ gcc -g hello.c -o hello

Comenzi specifice GDB

Cea mai folosită modalitate de a porni tool-ul de depanare este de a scrie gdb în terminal, urmat de numele executabilului ce se dorește a fi depanat.

  student@pracsis01 ~/Desktop $ gdb hello

O parte din comenzile cele mai utilizate ale GDB sunt următoarele (pentru lista completă studiați pagina de manual GDB - man gdb):

Opțiune	Efect
break [nume_fișier:] nume_funcție break [nume_fișier:] număr_linie	Setează un breakpoint (punct de întrerupere) la începutul funcției nume_funcție sau la linia specificată prin număr_linie din fișierul specificat prin nume_fișier.
run [listă_argumente]	Pornește programul în execuție (cu lista de argumente, dacă au fost specificate).
bt	Backtrace: afișează stiva de program.
print expresie	Afișează valoarea unei expresii (valoarea stocată într-o variabilă, valoarea returnată de o funcție etc.).
c	Continuă execuția programului (după ce a fost oprit, spre exemplu după un breakpoint).
next	Execută următoarea linie de program (după oprire), sărind peste orice apel de funcție care se găsește în această linie.
list [nume_fișier:] nume_funcție	Afișează liniile de cod ale programului din vecinătatea locului unde este oprit acum.
step	Execută următoarea linie de program (după oprire), intrând în orice funcție apelată de acea linie.
help [nume]	Afișează informații despre comanda GDB nume sau informații generale despre utilizarea GDB.
quit	Iese din GDB.

Observație: Cele mai multe dintre aceste comenzi pot fi apelate doar prin prima literă a numelui lor.

Spre exemplu, următoarea comandă:

  (gdb) next

este identică cu:

  (gdb) n

Observație: Dacă se apasă pe enter fără a scrie o comandă, se repetă ultima comandă specificată.

Exemplu de depanare

Se dă fișierul sursă suma_fact.c, care conține următoarele instrucțiuni:

#include<stdio.h>

unsigned int factorial(int n){
    if(n==0){
        return 1;
    }
    int i;
    unsigned int fact=0;
    for(i=1; i<=n; i++){
        fact *= i;
    }
    return fact;
}


int main(){
    int n, i;
    do{
        printf("Introduceti un numar natural mai mic sau egal cu 8:");
        scanf("%d", &n);
    }while(n<0 || n>8);
    unsigned int suma = 0;
    for(i=0; i<=n; i++){
        suma += factorial(i);
    }
    printf("%u\n", suma);
    return 0;
}

Programul își propune să calculeze suma factorialelor de la 0 la n, unde n este introdus de la tastatură. Dacă rulăm programul vom obține ca rezultat numărul 1, indiferent de ce a fost introdus de la tastatură. Ne propunem să descoperim bug-ul folosind GDB.
Compilăm sursa, adăugând simboluri de debug în executabil, după care lansăm în execuție debugger-ul:

  student@pracsis01 ~/Desktop $ gcc -g suma_fact.c -o suma_fact
  student@pracsis01 ~/Desktop $ gdb suma_fact

Atenție: Comanda de mai sus lansează în execuție numai debugger-ul, nu și programul suma_fact.

Observație: Putem observa că am pornit debugger-ul prin faptul că fiecare rând nou din linia de comandă începe acum astfel:

  (gdb)

Punem un breakpoint la linia 19, unde se afișează în consolă (prima comandă propriu-zisă):

  (gdb) b 19

Pornim programul în interiorul debugger-ului:

  (gdb) run
  Starting program: /home/student/work/lab10/suma_fact
   
  Breakpoint 1, main () at suma_fact.c:19
  19	        printf("Introduceti un numar natural mai mic sau egal cu 8:");
  (gdb)