T.T. Cociaș
Programarea Calculatoarelor și Limbaje de Programare / Laborator
LABORATORUL 10

Funcții în C/C++

Durată: 2 ore Limbaj: C / C++ Precedent: Laboratorul 9 PDF îndrumar EN English version

Un program C/C++ este o colecție de module distincte numite funcții. Împărțirea codului în funcții mici, fiecare cu o responsabilitate clară, este principalul instrument de control al complexității: face codul reutilizabil, testabil și mult mai ușor de citit.

1Obiectivele lucrării

stiva creste in jos la fiecare apel si se retrage la fiecare returnmain()variabile locale ale lui mainf()parametri + locale + adresa de revenireg()cadrul curent - varful stiveiapelapelreturn
Fig. - Stiva de apeluri. Fiecare apel adauga un cadru cu parametrii, variabilele locale si adresa de revenire; la return, cadrul dispare, iar variabilele lui nu mai exista.
  • Scrierea definițiilor și a prototipurilor de funcții
  • Distingerea transmiterii prin valoare de cea prin adresă
  • Înțelegerea mecanismului stivei de apel
  • Aplicarea corectă a domeniilor de vizibilitate
  • Implementarea funcțiilor recursive și recunoașterea limitelor lor
  • Folosirea supraîncărcării și a parametrilor impliciți din C++

2Definiție și prototip

sintaxa definiției
tip_rez nume_functie (lista_parametri)
{
    <declaratii locale>
    secventa de instructiuni
}
ElementRolObservații
tip_reztipul valorii returnateimplicit int; se scrie void dacă nu se returnează nimic
nume_functieidentificatorrespectă regulile identificatorilor
lista_parametrideclarații de forma tip numese separă prin virgulă; void sau gol dacă nu există
prototip vs. definiție
// PROTOTIP (declaratie) - spune compilatorului ce sa astepte
double aria(double raza);          // se pune inainte de main, in zona globala

int main(void) {
    printf("%.2f\n", aria(2.5));   // apelul este acum valid
    return 0;
}

// DEFINITIE - corpul propriu-zis, poate fi si in alt fisier
double aria(double raza) {
    return 3.14159 * raza * raza;
}
De ce este nevoie de prototipCompilatorul citește fișierul de sus în jos. Fără prototip, la întâlnirea apelului nu știe câți parametri are funcția și de ce tip, deci nu poate verifica corectitudinea. Prototipul rezolvă problema fără a impune o anumită ordine a definițiilor.
Funcțiile nu se pot imbricaÎn C/C++, spre deosebire de Pascal, o funcție nu poate fi definită în interiorul alteia. Toate definițiile sunt la același nivel.

3Transmiterea parametrilor

ModCe primește funcțiaModifică originalul?Cost
Prin valoareo copie a valoriinucopierea datelor
Prin pointeradresa variabileidadoar o adresă
Prin referință (C++)un alias al variabileidadoar o adresă
Tablouîntotdeauna adresa primului elementdadoar o adresă
Tablourile fac excepțieUn tablou nu se copiază niciodată la apel. Chiar dacă parametrul este scris int v[], funcția primește un pointer, deci modificările se reflectă în tabloul original. Din același motiv, sizeof aplicat parametrului dă dimensiunea unui pointer, nu a tabloului - dimensiunea trebuie transmisă separat.

4Simulator: stiva de apel

Urmăriți ce se întâmplă cu variabilele când se apelează o funcție: se creează copii pe stivă, iar la revenire acestea dispar. Observați de ce prima variantă nu modifică nimic.

Prin valoare vs. prin pointer

5Domeniu de vizibilitate

Tip de variabilăVizibilă înTrăiește
Locală (automată)blocul în care e declaratăpână la ieșirea din bloc
Parametru formalcorpul funcțieipe durata apelului
Locală staticblocul în care e declaratătot programul
Globalătot fișierul, după declarațietot programul
Mascarea numelorO variabilă locală cu același nume ca una globală o „ascunde" în interiorul blocului. Globala rămâne accesibilă în C++ prin operatorul de scop: ::nume.
Evitați variabilele globaleEle pot fi modificate din orice punct al programului, ceea ce face imposibilă urmărirea sursei unei erori. Preferați transmiterea explicită prin parametri.

6Recursivitate

O funcție recursivă se apelează pe ea însăși. Orice funcție recursivă trebuie să aibă:

  1. un caz de bază, care se rezolvă direct, fără apel recursiv;
  2. un pas recursiv care se apropie de cazul de bază la fiecare apel.
Fără caz de bază → stack overflowFiecare apel consumă spațiu pe stivă. Dacă recursivitatea nu se oprește, stiva se epuizează și programul se închide brutal.
ProblemăRecursivIterativ
Factorialelegant, dar consumă stivămai eficient
Fibonacci naivfoarte lent - O(2ⁿ), recalculează aceleași valoriO(n)
Parcurgerea arborilornatural și clarnecesită stivă explicită
Turnurile din Hanoisoluția evidentăcomplicat

7Facilități suplimentare în C++

FacilitateDescriereExemplu
Supraîncărcaremai multe funcții cu același nume, dar parametri diferițiint max(int,int) și double max(double,double)
Parametri implicițivalori folosite dacă argumentul lipsește la apelvoid f(int a, int b = 10)
Funcții inlinecodul se inserează la locul apeluluiinline int patrat(int x)
Referințetransmitere fără copiere, cu sintaxă simplăvoid f(int &x)
Reguli pentru supraîncărcareFuncțiile trebuie să difere prin numărul sau tipul parametrilor. Diferența doar prin tipul returnat nu este suficientă - compilatorul nu ar putea alege. Parametrii impliciți se pun doar la sfârșitul listei.

8Cod sursă

functii_baza.c - prototipuri și apeluri
#include <stdio.h>

// prototipuri
double aria(double raza);
int    maxim(int a, int b);
void   afiseazaLinie(char c, int n);
void   minMax(int v[], int n, int *min, int *max);

int main(void)
{
    afiseazaLinie('=', 40);
    printf("Aria pentru r=2.5: %.4f\n", aria(2.5));
    printf("Maximul dintre 17 si 42: %d\n", maxim(17, 42));

    int v[] = {29, 10, 14, 37, 5};
    int mn, mx;
    minMax(v, 5, &mn, &mx);        // doua rezultate prin pointeri
    printf("Minim=%d  Maxim=%d\n", mn, mx);

    afiseazaLinie('=', 40);
    return 0;
}

double aria(double raza) { return 3.14159265 * raza * raza; }

int maxim(int a, int b) { return (a > b) ? a : b; }

void afiseazaLinie(char c, int n)
{
    for (int i = 0; i < n; i++) putchar(c);
    putchar('\n');
}

void minMax(int v[], int n, int *min, int *max)
{
    *min = *max = v[0];
    for (int i = 1; i < n; i++) {
        if (v[i] < *min) *min = v[i];
        if (v[i] > *max) *max = v[i];
    }
}
recursivitate.c - comparație cu varianta iterativă
#include <stdio.h>

long factorialRec(int n)
{
    if (n <= 1) return 1;              // CAZ DE BAZA - obligatoriu
    return n * factorialRec(n - 1);    // pas recursiv
}

long factorialIter(int n)
{
    long r = 1;
    for (int i = 2; i <= n; i++) r *= i;
    return r;
}

long fibonacciRec(int n)               // ATENTIE: exponential de lent
{
    if (n <= 1) return n;
    return fibonacciRec(n - 1) + fibonacciRec(n - 2);
}

long fibonacciIter(int n)              // liniar, mult mai rapid
{
    long a = 0, b = 1, t;
    for (int i = 0; i < n; i++) { t = a + b; a = b; b = t; }
    return a;
}

int cmmdc(int a, int b)                // algoritmul lui Euclid
{
    if (b == 0) return a;
    return cmmdc(b, a % b);
}

int main(void)
{
    printf("10! recursiv = %ld\n", factorialRec(10));
    printf("10! iterativ = %ld\n", factorialIter(10));
    printf("Fibonacci(20) = %ld\n", fibonacciIter(20));
    printf("cmmdc(48, 18) = %d\n", cmmdc(48, 18));
    return 0;
}
supraincarcare.cpp - facilități C++
#include <iostream>
using namespace std;

// aceeasi denumire, parametri diferiti
int    maxim(int a, int b)             { return (a > b) ? a : b; }
double maxim(double a, double b)       { return (a > b) ? a : b; }
int    maxim(int a, int b, int c)      { return maxim(maxim(a, b), c); }

// parametri impliciti - doar la sfarsitul listei
void afiseaza(const char *text, int repetari = 1, char separator = '\n')
{
    for (int i = 0; i < repetari; i++)
        cout << text << separator;
}

// transmitere prin referinta
void dubleaza(int &x) { x *= 2; }

int main()
{
    cout << maxim(3, 7)        << endl;     // varianta int
    cout << maxim(3.5, 7.1)    << endl;     // varianta double
    cout << maxim(3, 7, 5)     << endl;     // varianta cu trei parametri

    afiseaza("Salut");                      // foloseste valorile implicite
    afiseaza("Test", 3);                    // repeta de 3 ori
    afiseaza("A", 4, ' ');                  // separator personalizat
    cout << endl;

    int n = 21;
    dubleaza(n);
    cout << "n = " << n << endl;            // 42

    return 0;
}

9Atelier de cod

La funcții, panoul din dreapta arată stiva de apeluri: fiecare apel își are propriul set de variabile. La recursivitate se vede cum se adună cadrele unul peste altul.

Recursivitate - priviți stiva crescând
#include <stdio.h>

int factorial(int n)
{
    if (n <= 1) return 1;             /* cazul de oprire */
    return n * factorial(n - 1);      /* apelul recursiv  */
}

int fibonacci(int n)
{
    if (n < 2) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(void)
{
    printf("5! = %d\n", factorial(5));

    int i;
    printf("Fibonacci: ");
    for (i = 0; i < 10; i++) printf("%d ", fibonacci(i));
    printf("\n");
    return 0;
}
De încercatRulați pas cu pas și opriți-vă când sunt afișate mai multe cadre factorial() unul sub altul: fiecare are propriul n. Ștergeți condiția de oprire și veți vedea eroarea de stivă plină.
Exercițiu - cel mai mare divizor comun
#include <stdio.h>

/* Algoritmul lui Euclid, varianta iterativa:
   cat timp b este diferit de 0:
       retine restul lui a la b, apoi a devine b, iar b devine restul  */
int cmmdc(int a, int b)
{
    /* Completati corpul functiei */
    return 0;
}

int main(void)
{
    int a, b;
    printf("Doua numere: ");
    scanf("%d %d", &a, &b);
    printf("cmmdc(%d, %d) = %d\n", a, b, cmmdc(a, b));
    return 0;
}

10Sarcini de lucru

  • Scrieți funcții pentru aria și perimetrul cercului, dreptunghiului și triunghiului.
  • Implementați o funcție care returnează simultan minimul și maximul unui vector, prin pointeri.
  • Verificați experimental că o funcție cu parametru transmis prin valoare nu modifică originalul.
  • Scrieți factorialul recursiv și iterativ; comparați rezultatele pentru n = 20.
  • Măsurați timpul de execuție pentru Fibonacci recursiv și iterativ, la n = 40.
  • Implementați cel mai mare divizor comun prin algoritmul lui Euclid, recursiv.
  • Scrieți o funcție care primește un tablou și afișați sizeof în interiorul ei - explicați rezultatul.
  • În C++, supraîncărcați o funcție de calcul al mediei pentru 2, 3 și 4 argumente.

11Aplicație de aprofundare

ExtindereImplementați problema Turnurilor din Hanoi cu afișarea fiecărei mutări și numărarea lor. Verificați experimental formula 2ⁿ − 1. Adăugați apoi un contor global al adâncimii de recursivitate și afișați adâncimea maximă atinsă. Comparați numărul de apeluri pentru Fibonacci recursiv naiv cu varianta memoizată (care reține rezultatele deja calculate într-un tablou).

12Întrebări de verificare

13Resurse