Capitolul 4.10. Recursivitate

Functiile din C pot fi folosite recursiv. Aceasta inseamna ca o functie se poate apela pe insasi, fie direct fie indirect. Un exemplu traditional este cel relativ la tiparirea unui numar ca si sir de caractere. Asa cum am mentionat mai inainte, cifrele sint generate intr-o ordine gresita: cele mai putin semnificative sint dispuse inaintea celor mai semnificative iar tiparirea lor se face invers.
Exista doua solutii pentru aceasta problema. Una este de a memora cifrele intr-un tablou asa cum au fost generate, apoi sa le tiparim in ordine inversa asa cum am facut in cap 3 cu itoa. Prima versiune a lui printd foloseste acest model.

printd(n) /* print n in decimal */
int n;
{
char s[10];
int i;
if (n < 0) {
putchar('-');
n = -n;
}
i = 0;
do {
s[i++] = n % 10 + '0'; /* get next char */
} while ((n /= 10) > 0); /* discard it */
while (--i >= 0)
putchar(s[i]);
}

Alternativa este o solutie recursiva, in care fiecare apelare a lui printd intii se autoapeleaza pentru a trata cifrele din fata, apoi tipareste cifra din coada.

printd(n) /* print n in decimal(recursive) */
int n;
{
int i;
if (n < 0) {
putchar('-');
n = -n;
}
if ((i = n/10) != 0)
printd(i)
putchar(n % 10 + '0');
}

Cind o functie se autoapeleaza fiecare invocare genereaza un set proaspat de variabile automate absolut independent de setul precedent. Astfel in printd(123) primul printd are n=123. Acesta trece 12 celui de-al doilea printd, apoi tipareste 3 cind acesta din urma revine. In axcelasi fel, urmatorul printd trece 1 la al treilea apoi tipareste 2.

Recursivitatea nu duce in general la economie de memorie atita timp cit trebuie mentinuta o stiva cu valorile ce urmeaza a fi procesate . Codul recursiv este mai compact si adesea mai usor de scris si inteles. Recursivitatea este convenabila in special pt structuri de date recursive precum arborii; vom vedea un exemplu dragut in capitolul 6.

Exercitiul 4.7. Adaptati ideile de la printd pt a scrie o versiune recursiva a lui itoa; adica de a converti un intreg intr-un sir printr-o rutina recursiva.

Exercitiul 4.8. Scrieti o versiune recursiva a functiei reverse(s) care inverseaza sirul s.