Recursivitate în C++: apeluri, afișare și rezultat

O funcție este recursivă dacă se apelează pe ea însăși, direct sau prin alte funcții. Pentru ca execuția să se încheie, ai nevoie de un caz care nu mai face apeluri și de argumente care ajung la acel caz.

În exemplul de mai jos, domeniul este cel al numerelor naturale. Condiția n == 0 oprește funcția, iar n - 1 apropie fiecare apel de oprire. Pentru un n negativ, aceeași scădere nu ajunge la zero. Prezența unui if nu dovedește singură că funcția se termină.

Fiecare apel are propria valoare a parametrului transmis prin valoare. Când apelul interior primește 0, parametrul apelului exterior nu devine și el 0.

Presupunem că programul include <iostream>.

void scrie(int n) {
  if (n == 0) return;
  std::cout << n;
  scrie(n - 1);
  std::cout << n;
}

Prima afișare se execută înainte de coborâre. A doua se execută după ce funcția interioară a revenit. Pentru scrie(2), etapele sunt:

1. Apelul cu 2 afișează 2 și îl pornește pe cel cu 1.
2. Apelul cu 1 afișează 1 și îl pornește pe cel cu 0.
3. Apelul cu 0 revine fără afișare.
4. Apelul cu 1 își execută a doua afișare: 1.
5. Apelul cu 2 își execută a doua afișare: 2.

Rezultatul este 2112, fără spații, deoarece codul nu afișează separatori.

O instrucțiune return trimite o valoare apelantului; std::cout scrie în ieșire. Urmărește-le separat.

int suma(int n) {
  if (n == 0) return 0;
  return n + suma(n - 1);
}

Pentru suma(4), la revenire obții succesiv 0, 1, 3, 6 și 10. Funcția returnează 10, dar nu afișează nimic. Domeniul exemplului este n >= 0, cu suma reprezentabilă în int.

Dacă un parametru este transmis prin referință sau funcția modifică o variabilă globală, apelurile pot schimba aceeași valoare. Nu aplica automat regulile parametrilor transmiși prin valoare.

Pentru funcția scrie, pornind de la $n \geq 0$, există $n+1$ apeluri, deoarece îl numeri și pe cel cu 0. Sunt $2n$ operații de afișare. Adâncimea maximă este $n+1$, deci memoria auxiliară a stivei este $O(n)$ în modelul obișnuit de execuție.

Două apeluri recursive în același corp pot schimba complet costul. Dacă fiecare apel cu $n>0$ apelează de două ori funcția cu $n-1$, numărul total respectă $A(n)=1+2A(n-1)$ și $A(0)=1$, deci $A(n)=2^{n+1}-1$. Adâncimea rămâne liniară, deși numărul total de apeluri este exponențial.

Pentru bucle și ordine de creștere, continuă cu complexitatea algoritmilor.

Pentru funcția scrie definită mai sus, determină textul afișat de scrie(3), numărul total de apeluri și numărul de afișări.

La coborâre, apelurile cu 3, 2 și 1 afișează 321. Apelul cu 0 nu afișează nimic. La revenire, apelurile cu 1, 2 și 3 afișează 123.

Textul complet este 321123. Apelurile sunt scrie(3), scrie(2), scrie(1) și scrie(0): 4 apeluri în total. Fiecare dintre cele trei apeluri cu parametru pozitiv afișează de două ori, deci sunt 6 afișări.

Control: dacă muți prima afișare după apel, ambele afișări au loc la revenire și obții 112233. Ordinea instrucțiunilor face parte din problemă.