Recursivitate în C++ pentru Bacalaureat

Definiții, tipare clasice (factorial, Fibonacci, sumă cifre, putere rapidă, căutare binară), probleme cu <iostream>, <cmath> și exemple cu using namespace std;.

Repere

Base casecondiție de oprire
Progressspre bază
Mergecombinare rezultate

Ce acoperim

  • Definiție, avantaje/dezavantaje, profunzime stivă (stack).
  • Tipare: liniară, ramificată, divizare (divide et impera).
  • Complexități: O(n), O(log n), O(2^n) (Fibonacci simplu).

Teorie – noțiuni esențiale

O funcție recursivă se apelează pe ea însăși, până la o condiție de oprire (caz de bază). Fără caz de bază → recursie infinită / eroare de stivă.
  • Caz de bază: situație trivială cu rezultat direct (ex. n<=1 la factorial).
  • Pas recursiv: reducerea problemei spre un caz mai mic (ex. n→n-1).
  • Divizare: împărțirea în subprobleme (ex. căutare binară: jumătate din vector).

Greșeli frecvente / Pitfalls

  • Fără bază sau progres greșit → buclă recursivă.
  • Refolosirea rezultatelor (memoizare) la Fibonacci.
  • Tipuri potrivite (overflow la factorial, folosește long long).

Factorial (liniar)

#include <iostream>
using namespace std;

long long fact(int n){
  if(n < 0) return 0;       // convenție simplă
  if(n <= 1) return 1;      // caz de bază
  return 1LL * n * fact(n-1);
}

int main(){
  int n; cin >> n;
  cout << fact(n) << '\n';
}

Sumă cifre (ramificare minimă)

#include <iostream>
using namespace std;

int sdig(int n){
  if(n < 10) return n;
  return n%10 + sdig(n/10);
}

int main(){
  int n; cin >> n;
  cout << sdig(n) << '\n';
}

Putere rapidă (divide et impera) + <cmath>

#include <iostream>
#include <cmath>
using namespace std;

long long powi(long long a, long long n){
  if(n == 0) return 1;
  if(n % 2 == 0){ long long t = powi(a, n/2); return t*t; }
  return a * powi(a, n-1);
}

int main(){
  cout << powi(2, 10) << " vs cmath " << (long long)pow(2,10) << '\n';
}

Fibonacci – simplu vs. memoizare

#include <iostream>
using namespace std;

long long fib_slow(int n){             // O(2^n)
  if(n <= 1) return n;
  return fib_slow(n-1) + fib_slow(n-2);
}

long long memo[94];                     // până ~Fib(93)
long long fib_fast(int n){              // O(n)
  if(n <= 1) return n;
  if(memo[n]) return memo[n];
  return memo[n] = fib_fast(n-1) + fib_fast(n-2);
}

int main(){
  int n; cin >> n;
  cout << fib_fast(n) << '\n';
}

Căutare binară recursivă

#include <iostream>
using namespace std;

int bsearch_rec(int v[], int l, int r, int x){
  if(l > r) return -1;                  // baza: nu există
  int m = (l+r)/2;
  if(v[m] == x) return m;
  if(x < v[m]) return bsearch_rec(v, l, m-1, x);
  return bsearch_rec(v, m+1, r, x);
}

int main(){
  int v[] = {1,3,5,7,9,11}, n=6, x=7;
  cout << bsearch_rec(v,0,n-1,x) << '\n';
}

Turnurile din Hanoi (folosește pow pentru mișcări)

#include <iostream>
#include <cmath>
using namespace std;

void hanoi(int n, char from, char aux, char to){
  if(n == 0) return;
  hanoi(n-1, from, to, aux);
  cout << from << " -> " << to << '\n';
  hanoi(n-1, aux, from, to);
}

int main(){
  int n=3; hanoi(n,'A','B','C');
  cout << "Mutări minime: " << (long long)pow(2,n)-1 << '\n';
}

Test de evaluare – Recursivitate (10 întrebări)

Alege varianta corectă. Primești feedback și răspunsuri corecte.

1) Cazul de bază într-o funcție recursivă este…

2) Numărul minim de mutări la Hanoi cu n discuri:

3) Complexitatea lui fib_slow este:

4) Pentru a se termina, o recursie trebuie să…

5) sdig(2034) întoarce:

6) T(n)=T(n/2)+O(1) implică:

7) Alege varianta tail-recursive pentru suma 1..n:

8) Puterea rapidă (exponentiere prin pătrare) are complexitatea:

9) Pentru f(n){ if(n==0)return 0; return 1+f(n/2);} f(8)=

10) Care e riscul principal la recursie profundă?