Funcții recursive

Funcții recursive procedurale

Să analizăm următorul program:

#include <iostream>
using namespace std;
void show(int n) {
    if (n != 0) {
        cout << n;
display(n - 1);
    }
}
int main () {
    display(3);
    return 0;
}

Observăm că la definirea funcției, în corpul său, ea se autoapelează. Acesta este principalul mod în care se realizează recusivitatea. Vom vedea ulterior și alt mod, acela când o funcție ajunge să se autoapeleze nu direct ci prin intermediul altei funcții (recursivitate indirectă).

Să analizăm efectul acestui program. Majoritatea oamenilor dau răspunsul corect: se afișează 321.

Analizăm și exemplul următor:

void show(int n) {
if (n != 0) {
    cout << n;
    display(n - 1);
    cout << n;
    }
}

Rămâne contextul de mai sus, am modificat doar funcția, adăugând o instrucțiune de afișare după autoapel.

În acest caz, majoritatea oamenilor nu dau răspunsul corect :D . Iată în continuare o analiză detaliată, pas cu pas, a ceea ce se întâmplă:

Se observă așadar o simetrie, adică întâi se afișează 321, apoi 123, acestea fiind valorile parametrilor care ajung în stivă, prima dată în ordinea de parcurgere, apoi în ordine inversă. Vom adăuga funcției și ramura else, unde tipărim pe n. Adică:

void afisare(int n) {
	if (n!=0) {
		cout << n;
		display(n-1);
		cout << n;
	} else
		cout << n;
}

Ținând cont de analiza detaliată de mai sus, se ajunge să se tipărească și pe ramura else ceva, adică 0. Acest lucru se realizează după ce s-a terminat urcarea în stivă și înainte să se înceapă coborârea, adică după ce s-au parcurs parametrii într-o ordine și înainte să se înceapă parcurgerea lor invers. Astfel avem: 3210123.

Putem trage de pe acum concluzia: prin recursivitate avem posibilitatea parcurgerii unui set de date de două ori: o dată prin instrucțiunile de pe ramura cu autoapelul, aflate înainte de autoapel, apoi prin cele de pe ramura cu autoapelul aflate după autoapel, în ordine inversă a valorilor parametrilor față de prima parcurgere. Între cele două parcurgeri se execută o singură dată ce se află pe ramura else.

Înainte de a trage și alte concluzii, să analizăm ce se întâmplă și în cazul când funcția arată ca mai jos:

void afisare(int n) {
	cout << n;
	display(n-1);
}

Se tipărește: 3210 - 1 - 2 - 3 - 4 - 5 ...

Majoritatea oamenilor spun că se ciclează infinit și într-un fel este adevărat. La o analiză mai atentă, ținând cont de faptul că la fiecate autoapel se alocă memorie nouă în stivă, și observând că niciodată vreun autoapel nu se termină, tragem căncluzia că niciodată nu se eliberează memorie și se tot alocă. Atunci cănd spațiul rezervat zonei de stivă se epuizează programul se termină cu eroare la executare (Stack overflow error).

Trebuie deci avut grijă să condiționăm autoapelul și să ne asigurăm că ajungem cândva încât parametrii fac să nu se mai execute autoapel, moment în care începe întoarcerea, coborârera în stivă.

Există chiar o teoremă care afirmă că oricărei scrieri recursive îi corespunde una repetitivă și reciproc

Astfel, putem spune că, la modul general, o funcție recursivă este de forma

functie (parametrii) {
if (conditie) {
	instructiuni 1
	functie (valorile urmatoare ale parametrilor)
	Instructiuni 2
} else
	Instructiuni 3
}

• Se execută așadar de mai multe ori numai instrucțiuni1, cât timp valorile parametrilor fac condiția adevărată.
• Se execută apoi, o singură dată instrucțiuni3, în momentul în care valorile parametrilor fac condiția falsă.
• Se execută apoi instrucțiuni2, de același număr de ori ca și instrucțiuni1, dar în ordine inversă a valorilor parametrilor ca în cazul executărilor lui instrucțiuni1.

Altfel spus, liniarizând, avem:

Instrucțiuni 1
Instrucțiuni 1
...
Instrucțiuni 1
Instrucțiuni 3
Instrucțiuni 2
Instrucțiuni 2
...
Instrucțiuni 2

Am prezentat elementele cheie de la o funcție recursivă: faptul că autoapelul trebuie condiționat, că putem pune instruțiuni pe ramura cu autoapelul (înainte și după acesta) sau pe ramura cealaltă. Putem însă să adăugăm instrucțiuni chiar înaintea deciziei sau după ea. Un bun exercițiu în înțelegerea recursivității este să vă gândiți acum ce efect are un apel afisare(3) pentru funcția de mai jos:

void afisare(int n) {
cout << n;
if (n != 0) {
cout << n; //2
afisare(n - 1);
cout << n;//3
} else
cout << n; //4
cout << n; //5
} 

Efectul este afișarea următorului șir de valori: 3 3 2 2 1 1 0 0 0 1 1 2 2 3 3.

Așadar, instrucțiunea 1 fiind înainte de if ea se va executa la fiecare intrare în funcție deci și în cazul în care se continuă pe ramura cu autoapelul dar și în cazul când se merge pe cealaltă ramură. Așadar, dacă cea de dinainte de autoapel de pe ramura cu autoapelul se execută de trei ori, cea din fața lui if se execută odată în plus. Valorile îngroșate sunt cele afișate de ea: 3 3 2 2 1 1 0 0 0 1 1 2 2 3 3.

Simetric, instrucțiunea 5 se execută la fiecare ieșire din funcție, indiferent de ramura pe care se executase cod, deci se execută tot de 4 ori. Valorile îngroșate sunt cele afișate de ea: 3 3 2 2 1 1 0 0 0 1 1 2 2 3 3.

Exerciții și probleme rezolvate

1. Scrieți o funcție recursivă care afișează cifrele unui număr în ordinea în care apar, separate prin câte un spațiu. De exemplu, un apel f(352) va avea ca efect afișarea: 3 5 2.

void f(int n) {
	if (n != 0) {
		f(n / 10);
	cout << n % 10 << " ";
	}
}

Traversarea cifră cu cifră se face prin autoapel cu valoarea obținută eliminând ultima cifră. Întrucât algoritmul standard de parcurgere a cifrelor unui număr le obține de la dreapta, noi decidem să afișăm după autoapel cifra curentă (ultima), tipărindu-le astfel în ordinea de la stânga la dreapta

2. Scrieți o funcție recursivă cu parametru un număr n care afișează mai întâi descrescător valorile pare mai mici sau egale cu n, pe același rând, separate prin câte un spațiu, apoi afișează crescător, pe rândul următor valorile impare mai mici sau egale decât n. Se tipăresc doar valorile nautale nenule. De exemplu, un apel f(8) ar trebui să aibă efectul:

8 6 4 2
1 3 5 7

void f(int n) {
if (n != 0) {
	if (n % 2 == 0)
		cout << n << " ";
	f(n - 1);
	if (n % 2 != 0)
		cout << n << " ";
} else
	cout << "\n";
}

Noi traversăm mai întâi descrescător numerele de la n la 1 dar decidem să le afișăm doar pe cele pare, cu spații între ele. La revenire le afișam pe cele impare, tot cu spațiu între ele, deci le obținem în ordine crescătoare. Pe ramura else, al cărei cod se execută o singură dată, la mijloc, vom tipări un enter.

3. Considerăm următoarea secvență de cod:

cin >> n;
i = 1;
while (i <= n) {
	cout << i;
	i++;
}

Scrieți un program care rezlizează același lucru printr-o funcție recursivă.

#include <iostream>
using namespace std;
int n;
void f(int i) {
	if (i <= n){
	cout << i;
	f(i + 1);
	}
}
int main () {
	cin >> n;
	f(1);
return 0;
}

Scopul acestui exercițiu este acela de a arăta un mod de “traducere” dintr-un cod repetitiv, mai ușor de scris, în unul recursiv.

Observăm:

• Contorul repetiției - i - este parametru la recursivitate (variabila a cărei valori valori se modifică de la un autoapel la altul);
• Modul de actualizare pentru contor este în legătură cu modul de autoapel: i++

  i++ f(i + 1);

• Condiția de la repetiție este aceeași cu cea de la condiționarea autoapelului;
• Inițializarea contorului (i = 1) are drept corespondent modul de apel inițial ( f(1) ).
• Instruțiunea subordonată repetiției este cea care se dorește a se executa la fiecare autoapel (cout << i).

În momentul predării recursivității oamenii își pun întrebarea: de ce trebuie să mai învăț cum fac recursiv dacă am varianta repetitivă echivalentă? În plus, se observă ca la recursivitate se consumă și oarecare timp cu alocarea/eliberarea de memorie în stivă

Motivul principal (și decisiv) pentru care este extrem de importantă recursivitatea este dat de ușurința cu care putem trata problemele ce necesită structuri neliniare precum arbori, grafuri. Codul de a vizita repetitiv astfel de structuri este infinit mai dificil de scris decât prin recursivitate.