1
1. Suma cifrelor unui numar (recursiv)
Orice numar natural poate fi descompus astfel:
n = (n // 10) * 10 + (n % 10). Ultima cifra este n % 10, restul numarului este n // 10. Recursivitatea aplica acelasi proces pe n // 10, pana cand numarul devine 0.
Urmarire executie pentru suma_cifre(1234):
suma_cifre(1234) = 4 + suma_cifre(123)
suma_cifre(123) = 3 + suma_cifre(12)
suma_cifre(12) = 2 + suma_cifre(1)
suma_cifre(1) = 1 + suma_cifre(0)
suma_cifre(0) = 0 ← caz de baza
Rezultat: 1+2+3+4 = 10
# Recursivitate: suma cifrelor unui numar def suma_cifre(n): if n == 0: return 0 # caz de baza return n % 10 + suma_cifre(n // 10) print("suma_cifre(1234) =", suma_cifre(1234)) print("suma_cifre(999) =", suma_cifre(999)) print("suma_cifre(0) =", suma_cifre(0))
Output real (rulat cu python):
suma_cifre(1234) = 10 suma_cifre(999) = 27 suma_cifre(0) = 0
Complexitate: O(log10 n) — numarul de apeluri recursive = numarul de cifre ale lui n.
2
2. Suma elementelor unui sir (parcurgere recursiva)
Parcurgerea recursiva a unui sir inseamna: procesam elementul curent (indexul
i), apoi apelam recursiv pe restul sirului (indexul i+1). Cazul de baza: am ajuns dincolo de sfarsitul sirului (i == len(lst)).
# Recursivitate: suma elementelor unei liste def suma_lista(lst, i=0): if i == len(lst): return 0 # caz de baza: am trecut de sfarsit return lst[i] + suma_lista(lst, i + 1) v = [3, 1, 4, 1, 5, 9, 2, 6] print("lista:", v) print("suma_lista(v) =", suma_lista(v)) print("suma_lista([]) =", suma_lista([])) print("suma_lista([7]) =", suma_lista([7]))
Output real (rulat cu python):
lista: [3, 1, 4, 1, 5, 9, 2, 6] suma_lista(v) = 31 suma_lista([]) = 0 suma_lista([7]) = 7
Complexitate: O(n) — un apel pentru fiecare element. Adancimea stivei de recursie = n.
3
3. Ridicare la putere — simplu si rapid
Varianta simpla: be = b × be-1, cu b0 = 1. Complexitate O(e).
Exponentiere rapida (Divide et Impera): daca e este par, be = (be/2)2. Jumatatea se calculeaza o singura data! Complexitate O(log e).
Exponentiere rapida (Divide et Impera): daca e este par, be = (be/2)2. Jumatatea se calculeaza o singura data! Complexitate O(log e).
Comparatie pentru 210:
Simplu: 11 apeluri (putere(2,10)→putere(2,9)→…→putere(2,0))
Rapid: putere(2,10)→putere(2,5)→putere(2,4)→putere(2,2)→putere(2,1)→putere(2,0) = 6 apeluri (verificat instrumentat)
# Recursivitate: ridicare la putere (exponentiere rapida) def putere(b, e): if e == 0: return 1 # b^0 = 1 pentru orice b if e % 2 == 0: jum = putere(b, e // 2) return jum * jum # jum calculat O DATA, nu de doua ori! return b * putere(b, e - 1) print("putere(2, 10) =", putere(2, 10)) print("putere(3, 5) =", putere(3, 5)) print("putere(5, 0) =", putere(5, 0))
Output real (rulat cu python):
putere(2, 10) = 1024 putere(3, 5) = 243 putere(5, 0) = 1
Atentie:
jum = putere(b, e // 2) apoi jum * jum este corect. Daca am scrie direct putere(b, e//2) * putere(b, e//2), am apela functia de doua ori si am pierde avantajul! Adancimea stivei O(log e).
4
4. Divide et Impera: Cautarea binara
Strategia Divide et Impera: imparte problema in subprobleme mai mici, rezolva fiecare subproblema recursiv, combina rezultatele.
Cautare binara: pe un sir sortat, compara valoarea cautata cu elementul din mijloc. Daca e egal → gasit. Daca e mai mic → cauta in jumatatea stanga. Daca e mai mare → cauta in jumatatea dreapta. Complexitate: O(log n).
Cautare binara: pe un sir sortat, compara valoarea cautata cu elementul din mijloc. Daca e egal → gasit. Daca e mai mic → cauta in jumatatea stanga. Daca e mai mare → cauta in jumatatea dreapta. Complexitate: O(log n).
Urmarire pentru cautare 7 in [1,3,5,7,9,11,13,15]:
st=0, dr=7, mij=3, lst[3]=7 == 7 → gasit la pozitia 3
(in cel mai rau caz, cel mult log2(8)=3 pasi)
# Divide et Impera: cautare binara recursiva def cautare_binara(lst, val, st, dr): if st > dr: return -1 # nu a fost gasit mij = (st + dr) // 2 if lst[mij] == val: return mij # gasit la pozitia mij elif val < lst[mij]: return cautare_binara(lst, val, st, mij - 1) else: return cautare_binara(lst, val, mij + 1, dr) v = [1, 3, 5, 7, 9, 11, 13, 15] print("lista:", v) print("cautare 7 -> pozitia", cautare_binara(v, 7, 0, len(v)-1)) print("cautare 1 -> pozitia", cautare_binara(v, 1, 0, len(v)-1)) print("cautare 15 -> pozitia", cautare_binara(v, 15, 0, len(v)-1)) print("cautare 6 -> pozitia", cautare_binara(v, 6, 0, len(v)-1))
Output real (rulat cu python):
lista: [1, 3, 5, 7, 9, 11, 13, 15] cautare 7 -> pozitia 3 cautare 1 -> pozitia 0 cautare 15 -> pozitia 7 cautare 6 -> pozitia -1
5
5. Divide et Impera: MergeSort (sortare prin interclasare)
Principiu: imparte sirul in doua jumatati, sorteaza recursiv fiecare jumatate, interclaseaza cele doua jumatati sortate intr-un sir sortat final.
Complexitate: O(n log n) — log n niveluri de impartire, n operatii de interclasare la fiecare nivel.
Complexitate: O(n log n) — log n niveluri de impartire, n operatii de interclasare la fiecare nivel.
Schema impartirii pentru [5,2,8,1,9,3]:
[5,2,8,1,9,3]
[5,2,8] [1,9,3]
[5,2][8] [1,9][3]
[5][2] [1][9]
Interclasare: [2,5] [1,9] → [1,2,5,8] [1,3,9] → [1,2,3,5,8,9]
# Divide et Impera: MergeSort def mergesort(lst): if len(lst) <= 1: return lst # caz de baza: 0 sau 1 element mij = len(lst) // 2 stanga = mergesort(lst[:mij]) dreapta = mergesort(lst[mij:]) return interclaseaza(stanga, dreapta) def interclaseaza(a, b): rez = [] i = j = 0 while i < len(a) and j < len(b): if a[i] <= b[j]: rez.append(a[i]); i += 1 else: rez.append(b[j]); j += 1 return rez + a[i:] + b[j:] v = [5, 2, 8, 1, 9, 3] print("inainte:", v) sortat = mergesort(v) print("dupa: ", sortat)
Output real (rulat cu python):
inainte: [5, 2, 8, 1, 9, 3] dupa: [1, 2, 3, 5, 8, 9]
Comparatie cu BubbleSort: pentru n=1000, BubbleSort face ~500.000 comparatii, MergeSort face ~10.000. La n=1.000.000, diferenta devine uriasa.
6
6. Implementare C++ EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
La profilul intensiv implementezi acelasi algoritmi in C++. Diferente cheie: tipuri explicite (int, long long), tablouri in loc de liste, transmitere prin pointer.
Suma cifrelor in C++:
#include <iostream> using namespace std; int suma_cifre(int n) { if (n == 0) return 0; // caz de baza return n % 10 + suma_cifre(n / 10); } int main() { cout << "suma_cifre(1234) = " << suma_cifre(1234) << endl; cout << "suma_cifre(999) = " << suma_cifre(999) << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
suma_cifre(1234) = 10 suma_cifre(999) = 27
Exponentiere rapida in C++:
#include <iostream> using namespace std; long long putere(long long b, int e) { if (e == 0) return 1; if (e % 2 == 0) { long long jum = putere(b, e / 2); return jum * jum; // jum calculat o singura data } return b * putere(b, e - 1); } int main() { cout << "putere(2, 10) = " << putere(2, 10) << endl; cout << "putere(3, 5) = " << putere(3, 5) << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
putere(2, 10) = 1024 putere(3, 5) = 243
Cautare binara recursiva in C++:
#include <iostream> using namespace std; int cautare_binara(int v[], int n, int val, int st, int dr) { if (st > dr) return -1; // nu a fost gasit int mij = (st + dr) / 2; if (v[mij] == val) return mij; if (val < v[mij]) return cautare_binara(v, n, val, st, mij - 1); return cautare_binara(v, n, val, mij + 1, dr); } int main() { int v[] = {1, 3, 5, 7, 9, 11, 13, 15}; int n = 8; cout << "cautare 7 -> pozitia " << cautare_binara(v, n, 7, 0, n-1) << endl; cout << "cautare 6 -> pozitia " << cautare_binara(v, n, 6, 0, n-1) << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
cautare 7 -> pozitia 3 cautare 6 -> pozitia -1
Aceleasi rezultate ca in Python — algoritmul este identic, sintaxa difera.