Diferență între revizuiri ale paginii „PC Laborator 10”
(Nu s-au afișat 12 versiuni intermediare efectuate de alți 2 utilizatori) | |||
Linia 17: | Linia 17: | ||
=== Exemplu de recursivitate directă === | === Exemplu de recursivitate directă === | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
− | int factorial(int n){ | + | int factorial(int n) { |
− | if(n<0){ | + | if (n < 0) { |
return 0; | return 0; | ||
− | }else if(n==0){ | + | } else if (n == 0) { |
return 1; | return 1; | ||
} | } | ||
int rez; | int rez; | ||
− | rez = n*factorial(n-1); | + | rez = n * factorial(n - 1); |
return rez; | return rez; | ||
} | } | ||
Linia 30: | Linia 30: | ||
=== Exemplu de recursivitate indirectă === | === Exemplu de recursivitate indirectă === | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
− | int factorial(int n){ | + | int factorial(int n) { |
− | if(n<0){ | + | if (n < 0) { |
return 0; | return 0; | ||
− | }else if(n==0){ | + | } else if (n == 0) { |
return 1; | return 1; | ||
} | } | ||
int rez; | int rez; | ||
− | rez = inmul_fact(n, n-1); | + | rez = inmul_fact(n, n - 1); |
return rez; | return rez; | ||
} | } | ||
− | int inmul_fact(int a, int b){ | + | int inmul_fact(int a, int b) { |
int prod; | int prod; | ||
− | prod = a*factorial(b); | + | prod = a * factorial(b); |
return prod; | return prod; | ||
} | } | ||
Linia 104: | Linia 104: | ||
#include<stdio.h> | #include<stdio.h> | ||
− | unsigned int factorial(int n){ | + | unsigned int factorial(int n) { |
− | if(n==0){ | + | if (n == 0) { |
return 1; | return 1; | ||
} | } | ||
int i; | int i; | ||
− | unsigned int fact=0; | + | unsigned int fact = 0; |
− | for(i=1; i<=n; i++){ | + | for (i = 1; i <= n; i++){ |
fact *= i; | fact *= i; | ||
} | } | ||
Linia 117: | Linia 117: | ||
− | int main(){ | + | int main() { |
int n, i; | int n, i; | ||
− | do{ | + | do { |
printf("Introduceti un numar natural mai mic sau egal cu 8: "); | printf("Introduceti un numar natural mai mic sau egal cu 8: "); | ||
scanf("%d", &n); | scanf("%d", &n); | ||
− | }while(n<0 || n>8); | + | } while (n < 0 || n > 8); |
unsigned int suma = 0; | unsigned int suma = 0; | ||
− | for(i=0; i<=n; i++){ | + | for (i = 0; i <= n; i++) { |
suma += factorial(i); | suma += factorial(i); | ||
} | } | ||
Linia 192: | Linia 192: | ||
'''$1 = 0''' | '''$1 = 0''' | ||
'''(gdb) ''' | '''(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 ''' | ||
+ | '''<span style="color: green">student@pracsis01</span> <span style="color: blue">~/Desktop $</span>''' | ||
+ | <div class="regula"> ''' 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''.</div> | ||
+ | |||
+ | == Exerciții == | ||
+ | <ol><li>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.</li> | ||
+ | <li>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.</li> | ||
+ | <li>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.</li> | ||
+ | <li>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ă.</li> | ||
+ | <li>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.</li> | ||
+ | <li>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.</li> | ||
+ | |||
+ | </ol> |
Versiunea curentă din 14 decembrie 2016 16:35
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ă.
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".
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. |
Spre exemplu, următoarea comandă:
(gdb) next
este identică cu:
(gdb) n
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
(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 $
Exerciții
- 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.
- 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.
- 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.
- 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ă.
- 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.
- 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.