Recursivitate

Un subprogram este recursiv dacă se autoapelează direct sau prin intermediul altor subprograme.

  Recursivitatea în C++ reprezintă capacitatea unui subprogram de a se defini prin el însuși.

    Exemple de operații recursive:
  • puteri: an = a * an-1 = a * a * an-2 = ...
  • factorial: n! = n * (n-1)! = ...
  • suma cifrelor: SumCif(n) = n%10 + SumCif(n/10) = ...
  • șirul lui Fibonacci: Fib(n) = Fib(n-1) + Fib(n-2) = ...

Subprogramele recursive trebuie să conțină condiții de oprire (să trateze cel puțin un caz de bază).

  Știm că în momentul apelării unui subprogram se rezervă o zonă de memorie pentru variabilele locale din cadrul acelei funcții. Dacă se întâlnește un alt apel de funcție, se rezervă o nouă zonă și se execută acest subprogram nou. Efectul de stivă face imposibilă întoarcerea în subprogramul inițial până la sfârștul subprogramului actual (implicit ștergerea variabilelor locale din memorie).

Exemplu

  Pentru aflarea puterii an, putem descrie două tipuri de programe:
● Varianta nerecursivă (iterativă)

int putere (int a, int n){
  int p=1;
  for(int i=1; i<=n; i++) p*=a;
  return p;
}

   În cazul în care lucrăm cu numere mari, această metodă iterativă poate să nu fie ideală, întrucât se poate să depășim intervalul de definiție al tipului de dată.

● Varianta recursivă

int putere (int a, int n){
  if(!n) return 1;
  return a * putere(a,n-1);
}

  La începutul oricărui subprogram recursiv trebuie să tratăm măcar un caz de bază, ca să nu executăm apeluri recursive la nesfârșit. În cazul nostru, atunci când numărul devine nul, vom returna valoarea 1 (valoarea returnată trebuie atent aleasă, în funcție de nevoi).
  Dacă nu este îndeplinit cazul de bază, vom returna o expresie. Această expresie este o înmulțire între valoarea a (baza puterii) primită ca parametru și un apel de funcție (aceeași bază, exponentul - 1).

  Pentru a=5 și n=4 următoarea schemă grafică arată pașii execuției apelului: putere(a,n);

putere(5,4) -> 5 * putere(5,3)
putere(5,3) -> 5 * putere(5,2)
putere(5,2) -> 5 * putere(5,1)
putere(5,1) -> 5 * putere(5,0)
putere(5,0) -> 1

  Când compilatorul începe executarea primului subprogram și ajunge la acel return cu o expresie, va încerca să calculeze expresia. Unul din factori fiind un subprogram, va începe executarea lui pentru a afla valoarea lui. Acesta având și el un apel recursiv, va tot executa subprograme până când va da de cazul de bază, când în sfârșit se opresc apelurile recursive.
  Luând concret pe cazul nostru, apelurile recursive se opresc la subprogramul putere(5,0), când al doilea parametru este nul și se returnează valoarea 1 (în loc de un apel recursiv). Am aflat valoarea subprogramului anterior menționat (s-a terminat executarea lui), deci ne întoarcem în putere(5,1). Din acest subprogram se returnează 5 * 1, și ne întoarcem la funcția anterioară (putere(5,2)). Tot așa până la sfârșit, când se va returna 625, practic rezultatul lui 54.


Afișarea în subprogramele recursive

  După cum știm, nu ne putem întoarce într-un subprogram precedent decât atunci când am terminat executarea celui actual (efectul de stivă). Astfel, dacă adăugăm o afișare în cadrul subprogramului, rezultatul va depinde de poziția față de apelul recursiv.
  Să le luăm pe rând:

1. Înainte de apelul recursiv

  Când afișarea se situează înainte de apelul recursiv, vom vedea rezultatele în ordinea în care se execută (apelează) subprogramele.

void f(int n){
  if(n){
    cout<<n%10;
    f(n/10);
  }
}

Dacă se citește n și se apelează f(n), avem următoarele rezultate:

123456
654321
97843
34879

  Acest subprogram afișează oglinditul lui n, fără a-l construi.

2. După apelul recursiv

  Dacă afișarea se află după apelul recursiv, se va afișa în ordinea inversă executării subprogramelor.

void f(int n){
  if(n){
    f(n/10);
    cout<<n%10;
  }
}

După citirea lui n și apelul f(n), se afișează:

123456
123456
5784654
5784654

  Față de afișarea înainte de apel, putem remarca că de această dată afișăm chiar numărul trimis ca parametru (cifrele în ordinea firească). Dacă urmărim pas cu pas, ne dăm seama că prima valoare afișată provine din ultimul subprogram apelat recursiv (penultimul dacă luăm în calcul și cel cu cazul de bază :D), afișare ce corespunde cu prima cifră a numărului.