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:

* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * *
* * * * * * * * * * *
* * * * * * *
* * *

12.1 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).

12.2 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;
}
}

---