Pointeri catre functii
Limbajul C permite operarea cu variabile de tip pointer care contin adresa de inceput a codului executabil al unei functii. Forma generala de declarare a unui astfel de pointer catre o functie este urmatoarea:
tip_rezultat (*nume_pointer) ( lista_tip_parametrii );
Observatie: La declararea unei functii care returneaza un pointer, spre deosebire de declararea unui pointer catre o functie, nu se utilizeaza paranteze rotunde. De exemplu:
float *f (float a, float b); /* functie */
float (*p)(float a, float b); /* pointer */
Adresa unei functii se obtine daca unui pointer de functii, compatibil ca tip si parametrii cu functia, i se atribuie numele functiei, fara ca acesta sa fie urmat de paranteze. De exemplu, pentru functia f si pointerul de functie p, din declaratia anterioara, se poate face atribuirea:
p=f; /* atribuire de functie catre un pointer compatibil */
Apelul functiei se face specificand, intre paranteze rotunde, operatorul "*" urmat de numele functiei si parametrii actuali. In cazul exemplului de mai sus, un apel este urmatorul:
float a,b,c;
c=(*p)(a,b); /* apel de functie */
Programul Pointeri catre o functie afiseaza suma, diferenta, produsul sau catul a doua numere reale a si b, utilizand pointerul de functie p caruia, succesiv, i se atribuie adresele unor functii compatibile: suma, dif, prod si cat.
Recursivitate
O functie este recursiva daca se autoapeleaza, direct sau indirect. In C toate functiile se pot defini recursiv.
Exemplu:
#include <stdio.h>
void numara(int n);
void main()
void numara(int n)
else
printf('Gata !n');
}
Dupa executia acestui program, pe ecran se va tipari
Gata!
Acest program s-ar fi
putut realiza si iterativ (folosind o instructiune de tip while).
Exemplu: Suma primelor n numere naturale.
int suma(int n)
De obicei, functiile recursive urmeaza un 'pattern' standard:
- exista un caz de baza (sau mai multe);
- caz recursiv general (in care, in general, un intreg este trimis ca argument al apelului recursiv);
Recursia este un procedeu foarte puternic de rezolvare a problemelor. Secretul este identificarea cazului general.
Pentru exemplul precedent, cand se trimite n catre functia 'suma()', recursivitatea activeaza n copii ale functiei inaintea intoarcerii pas cu pas catre primul apel recursiv (se mai spune ca in momentul apelului recursiv, variabilele locale "ingheata', ele 'dezghetandu-se' la intoarcerea din recursie). Multe functii recursive se pot scrie intr-o forma iterativa (folosind structuri de tip 'while'). Recursivitatea se recomanda cand problema se poate rezolva foarte usor folosind-o si cand nu se cere o eficienta sporita in timpul executiei programului. Uneori, se recomanda recursia finala (adica dupa apelul recursiv nu mai sunt alte instructiuni si nu exista variabile locale).
Exemplu: Citeste o linie si o afiseaza in ordine inversa, apoi lasa doua randuri goale
#include <stdio.h>
void tipareste(void);
void main()
void tipareste(void)
Iata o rulare in executie:
Introduceti o linie: invat sa programez
Observati in exemplul precedent ca la fiecare apel recursiv, se memoreaza in stiva caracterul 'c' legat la o valoare, care se va afisa la intoarcerea din recursie. Deci practic, sunt 'n' copii ale lui 'c', unde 'n' reprezinta lungimea liniei
Exemplu:Putem complica putin exemplul precedent, in sensul ca afisam aceleasi cuvinte, dar in ordine inversa.
include <ctype.h>
#include <stdio.h>
#define MAXWORD 100
void tipareste_cuvinte(void);
void citeste_cuvant(char *);
void main()
void tipareste_cuvinte(void)
void citeste_cuvant(char *s)
Daca, la executie, utilizatorul scrie:
Introduceti o linie: noi invatam C
atunci pe ecran, va apare:
C invatam noi
Variabila 'c' avand clasa de memorare 'static', rezulta ca valoarea ei se pastreaza de la un apel la altul. De altfel, initializarea lui 'c' se face o singura data (cand se intra prima data in aceasta functie). Daca 'c' ar fi fost de tip 'auto', atunci chiar daca aveam la sfarsitul sirului 'n', la urmatorul apel, acesta nu ar fi fost cunoscut, deci practic nu mai aveam conditie de oprire.
Exemplu:
In acest exemplu, vom desena 'pattern-uri' pe ecran folosind
functii recursive.
#include <stdio.h>
#define SYMBOL '*'
#define OFFSET 0
#define LENGTH
void display(char, int, int);
void draw(char, int);
void main()
void display(char c, int m, int n)
}
void draw(char c, int k)
}
Functia 'main()' contine apelul functiei
'display()', care apeleaza 'draw()', care la randul ei
apeleaza 'display()'. Deci functia
'display()' este recursiva. Functia 'draw()'
tipareste k copii ale caracterului 'c'. Pe ecran se va afisa:
* * * * * * * * * * * * * * *
* * * *
* * *
* * * * * * * * * * * *
* * * * * * * * * * *
* * * * * * *
* * *
Manipularea sirurilor folosind recursivitatea
Un sir consta dintr-un numar de caractere consecutive, terminate prin caracterul '0'. De fapt, putem gandi un sir ca fiind sirul nul (care consta doar din caracterul '0') sau un caracter urmat de un sir. Aceasta definitie a sirului este o structura de date recursiva.
Exemplu: O definitie recursiva a lungimii unui sir.
int r_strlen(char *s)
Aceasta formulare are dezavantajul pierderii in timpul executiei. Daca sirul
are lungimea k, calcularea lungimii sale necesita k + 1 apeluri recursive (un
compilator optimizat poate evita aceasta pierdere).
Metodologia 'divide-et-impera'
Recursivitatea se foloseste in foarte multe cazuri pentru codificarea algoritmilor 'divide-et-impera'. Un astfel de algoritm imparte problema in sub-probleme, rezolvand fiecare sub-problema prin recursie, apoi recombina solutiile partiale pentru a obtine intreaga solutie.
Consideram un exemplu cunoscut, si anume, determinarea minimului si maximului elementelor unui sir de intregi considerat cel mai bun algoritm pentru aceasta problema. Criteriul pentru 'cel mai bun' a fost numarul de comparatii necesare. Prezentam mai jos o functie C care rezolva aceasta problema (considerand dimensiunea sirului putere a lui 2).
void minmax(int a[], int n, int *min_ptr, int *max_ptr)
else
else
}
|
