>> Inapoi <<
============
Capitolul 12
============
========
Recursie
========
O functie este recursiva daca se autoapeleaza, direct sau indirect. In C toate functiile se pot defini recursiv.
----------
Exemplu:
----------
#include
void numara(int n);
void main()
{
numara(10);
}
void numara(int n)
{
if (n)
{
printf("%d ! ", n);
numara(n - 1);
}
else
printf("Gata !\n");
}
Dupa executia acestui program, pe ecran se va tipari
10 ! 9 ! 8 ! 7 ! 6 ! 5 ! 4 ! 3 ! 2 ! 1 !
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)
{
if (n <= 1)
return n;
else
return (n + suma(n - 1));
}
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()", recursia
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", se mai spune "derecursivare"). Recursia se recomanda cand problema
se poate rezolva foarte usor folosind recursie 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
void tipareste(void);
void main()
{
printf("Introduceti o linie: ");
tipareste();
printf("\n\n");
}
void tipareste(void)
{
char c;
if ((c = getchar()) != '\n')
tipareste();
putchar(c);
}
Iata o rulare in executie:
Introduceti o linie: iepurasu usa rupei
iepur asu usarupei
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
#include
#define MAXWORD 100
void tipareste_cuvinte(void);
void citeste_cuvant(char *);
void main()
{
printf("Introduceti o linie: ");
tipareste_cuvinte();
printf("\n\n");
}
void tipareste_cuvinte(void)
{
char w[MAXWORD];
citeste_cuvant(w);
if (w[0] != '\n')
tipareste_cuvant();
printf("%s ", w);
}
void citeste_cuvant(char *s)
{
static char c = '\0';
if (c == '\n')
*s++ = c;
else
while (!isspace(c = getchar()))
*s++ = c;
*s = '\0';
}
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
#define SYMBOL '*'
#define OFFSET 0
#define LENGTH 19
void display(char, int, int);
void draw(char, int);
void main()
{
display(SYMBOL, OFFSET, LENGTH);
}
void display(char c, int m, int n)
{
if (n > 0)
{
draw(' ', m);
draw(c, n);
putchar('\n');
display(c, m + 2, n - 4);
}
}
void draw(char c, int k)
{
if (k > 0)
{
putchar(c);
draw(c, k - 1);
}
}
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 recursia
---------------------------------------------------
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)
{
if (*s == '\0')
return 0;
else
return (1 + r_strlen(s + 1));
}
Eleganta acestei formulari recursive este "platita" de o pierdere 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"
-----------------------------------------
Recursia se foloseste in foarte multe cazuri pentru codificarea algoritmilor
"divide-et-impera". Un astfel de algoritm imparte problema in subprobleme,
rezolvand fiecare subproblema prin recursie, apoi recombina solutiile partiale
pentru a obtine intreaga solutie.
Vom considera un exemplu cunoscut, si anume, determinarea minimului si
maximului elementelor unui sir de intregi (publicat pentru prima data de catre
Ira Pohl, "A Sorting Problem and Its Complexity", Communications of the ACM,
15, nr. 6, 1972) 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)
{
int min1, max1, min2, max2;
if (n == 2)
if (a[0] < a[1])
{
*min_ptr = a[0];
*max_ptr = a[1];
}
else
{
*min_ptr = a[1];
*max_ptr = a[0];
}
else
{
minmax(a, n/2, &min1, &max1);
minmax(a + n/2, n/2, &min2, &max2);
if (min1 < min2)
*min_ptr = min1;
else
*min_ptr = min2;
if (max1 < max2)
*max_ptr = max2;
else
*max_ptr = max1;
}
}
-----------------------------------------------
Exercitii propuse spre implementare
-----------------------------------------------
1. Scrieti o functie C recursiva echivalenta cu "strncmp()".
2. Scrieti o functie C recursiva care calculeaza media aritmetica a unui sir de numere reale.
3. Scrieti o functie C recursiva care calculeaza n!, unde n este un numar natural.
4. (Mutarea calului) Data o tabla de sah (8 x 8), sa se scrie o functie C
recursiva care descrie mutarile calului astfel incat orice pozitie sa fie
parcursa o singura data.