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 20, unde se citește valoarea lui n:

  (gdb) b 20
  Breakpoint 1 at 0x80484c2: file suma_fact.c, line 20.
  (gdb) 

Pornim programul în interiorul debugger-ului:

  (gdb) run
  Starting program: /home/student/Desktop/suma_fact
   
  Breakpoint 1, main () at suma_fact.c:20
  20	        scanf("%d", &n);
  (gdb) 

Trecem mai departe și introducem o valoare pentru n:

  (gdb) next
  Introduceti un numar natural mai mic sau egal cu 8: 6 
  21	    }while(n<0 || n>8);
  (gdb) 

Vom parcurge programul pas cu pas până la apelarea funcției factorial:

  (gdb) n
  22	    unsigned int suma = 0;
  (gdb) n
  23	    for(i=0; i<=n; i++){
  (gdb) n
  24	        suma += factorial(i);
  (gdb) s
  factorial (n=0) at suma_fact.c:4
  4	    if(n==0){
  (gdb) s
  5	        return 1;
  (gdb) s
  13	}
  (gdb) s
  main () at suma_fact.c:23
  23	    for(i=0; i<=n; i++){
  (gdb) s
  24	        suma += factorial(i);
  (gdb) s
  factorial (n=1) at suma_fact.c:4
  4	    if(n==0){
  (gdb) s
  8	    unsigned int fact=0;
  (gdb) s
  9	    for(i=1; i<=n; i++){
  (gdb) s
  10	        fact *= i;
  (gdb) s
  9	    for(i=1; i<=n; i++){
  (gdb) s
  12	    return fact;
  (gdb) print fact
  $1 = 0
  (gdb) 

Observăm că valoarea returnată de funcția factorial pentru orice număr nenul este 0. Acest lucru se datorează inițializării variabilei fact cu valoarea 0 la începutul funcției factorial. Putem ieși din debugger pentru a modifica linia 8 din fișierul sursă suma_fact.c:

  (gdb) q
  A debugging session is active.
   
    	Inferior 1 [process 4279] will be killed.
   
  Quit anyway? (y or n) y 
  student@pracsis01 ~/Desktop $

Observație: Pentru a putea intra în interiorul funcției factorial este absolut necesar să se folosească comanda step și nu comanda next care ar trece peste acea linie 24 fără a intra în corpul funcției factorial.

Exerciții

1. Să se citească de la tastatură un număr întreg fără semn n. Să se implementeze o funcție recursivă care returnează suma primelor n numere naturale și să se afișeze rezultatul apelării acestei funcții.
2. Scrieți o funcție recursivă care șterge dintr-un vector elementul de pe o anumită poziție; funcția primește ca parametri vectorul, numărul de elemente din vector și poziția elementului ce urmează a fi șters.
3. Să se citească de la tastatură un număr întreg fără semn n. Să se implementeze o funcție recursivă care calculează termenul de pe o poziție dată din șirul lui Fibonacci și să se afișeze primii n termeni, știind că șirul lui Fibonacci este definit astfel:
   • F(0) = 0;
   • F(1) = 1;
   • F(i) = F(i-1) + F(i-2), pentru i>=2.
4. Scrieți o funcție recursivă care calculează 2 la puterea n, unde n este un număr întreg fără semn introdus de la tastatură.
5. Scrieți o funcție recursivă care descompune un număr întreg fără semn n într-o sumă de puteri ale lui 2. Afișați această descompunere.
6. Scrieți o funcție recursivă care descompune un număr întreg fără semn n într-o sumă de termeni din șirul lui Fibonacci. Afișați termenii din care este compus numărul.