Invatare Atomica

Aplicatii recursive

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei invata sa aplici recursivitatea in probleme concrete: sume recursive, parcurgerea cifrelor unui numar, cautarea binara si sortarea prin interclasare (Divide et Impera).

Dupa aceasta lectie vei putea:

  • Sa scrii o functie recursiva pentru suma cifrelor unui numar
  • Sa calculezi recursiv suma elementelor unui sir
  • Sa implementezi ridicarea la putere recursiva (inclusiv exponentiere rapida)
  • Sa explici strategia Divide et Impera si sa o aplici in cautarea binara
  • Sa implementezi MergeSort si sa justifici complexitatea O(n log n)
  • (Intensiv) Sa implementezi aceleasi algoritmi in C++ cu tipuri explicite

Incearca singur!

Provocare:

Inainte sa citesti lectia, incearca sa scrii o functie recursiva care calculeaza suma cifrelor unui numar. De exemplu, pentru 1234 trebuie sa obtii 10 (1+2+3+4).

Hint: ultima cifra a lui n este n % 10, iar numarul fara ultima cifra este n // 10.

💡 Ai nevoie de un indiciu?

Cazul de baza: daca n == 0, suma este 0 (nu mai exista cifre).

Pasul recursiv: n % 10 iti da ultima cifra, iar n // 10 elimina ultima cifra. Suma totala = ultima_cifra + suma_cifre(numarul_ramas).

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).
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).
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.
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.

Exercitii practice

Exercitiul 1 (Nivel minim) — Urmarire executie

Urmareste executia pas cu pas a functiei suma_cifre(352): scrie toate apelurile recursive si valorile returnate, pana la cazul de baza. Ce valoare finala obtii?

Vezi rezolvarea

Urmarirea apelurilor pentru suma_cifre(352), pana la cazul de baza:

  1. suma_cifre(352) = 2 + suma_cifre(35)
  2. suma_cifre(35) = 5 + suma_cifre(3)
  3. suma_cifre(3) = 3 + suma_cifre(0)
  4. suma_cifre(0) = 0 — caz de baza, n a ajuns la 0

Acum se aduna rezultatele in ordine inversa, de la ultimul apel spre primul:

  1. suma_cifre(3) = 3 + 0 = 3
  2. suma_cifre(35) = 5 + 3 = 8
  3. suma_cifre(352) = 2 + 8 = 10

Valoarea finala: 10 (verificare: 3+5+2=10, suma cifrelor lui 352).

Exercitiul 2 (Nivel standard) — Produs recursiv

Scrie o functie recursiva produs_lista(lst, i=0) care calculeaza produsul elementelor din lista. Cazul de baza: i == len(lst) returneaza 1 (elementul neutru al inmultirii). Testeaza cu [2, 3, 4] (rezultat asteptat: 24) si cu [] (rezultat: 1).

Vezi rezolvarea

Functia urmeaza tiparul lui suma_lista din lectie, dar cu inmultire in loc de adunare, deci elementul neutru al cazului de baza este 1, nu 0:

def produs_lista(lst, i=0): if i == len(lst): return 1 return lst[i] * produs_lista(lst, i+1)

Verificare pentru [2, 3, 4]:

  1. produs_lista([2,3,4], 0) = 2 * produs_lista(..., 1)
  2. = 2 * (3 * produs_lista(..., 2))
  3. = 2 * (3 * (4 * produs_lista(..., 3)))
  4. caz de baza: i=3=len(lst), deci apelul returneaza 1
  5. rezultat: 2 * 3 * 4 * 1 = 24 — corect

Pentru []: i=0 este deja len([]), deci se intra direct in cazul de baza si rezultatul este 1.

Exercitiul 3 (Nivel performanta) — Numar de aparitii

Scrie o functie recursiva nr_aparitii(lst, val, i=0) care numara de cate ori apare val in lista lst. Testeaza cu [1,2,3,2,2,4] si val=2 (rezultat asteptat: 3). Apoi explica complexitatea (O de ce?). Bonus intensiv: reimplementeaza in C++ cu tablou si indice.

Vezi rezolvarea

Schema de rezolvare (nu solutia completa — o construiesti singur):

  1. Foloseste tiparul lui suma_lista: parametrul i avanseaza prin lista, cazul de baza i == len(lst) returneaza 0.
  2. La fiecare pas: daca lst[i] == val, adauga 1 la rezultatul apelului recursiv pe i+1; altfel continua recursiv fara sa adaugi nimic.
  3. Capcana: apelul recursiv pe i+1 trebuie facut in ambele ramuri, altfel recursivitatea nu avanseaza.

Complexitate: un apel recursiv per element, ca la suma_lista — O(n), n fiind lungimea listei.

Bonus C++: lectia nu trateaza explicit aceasta functie in C++, dar arata tiparul recursiv cu tablouri si pointeri (vezi suma_cifre si cautare_binara); foloseste-l pentru int nr_aparitii(int v[], int n, int val, int i).

Evaluare: caz de baza corect, apel pe i+1 in ambele ramuri, testul [1,2,3,2,2,4], val=2 da 3, complexitatea justificata nu doar afirmata.

Ce ai invatat astazi

  • Suma cifrelor unui numar: recursie pe n % 10 si n // 10, complexitate O(log n)
  • Parcurgere recursiva a unui sir cu indice i, complexitate O(n)
  • Exponentiere rapida prin injumatatirea exponentului par, complexitate O(log e)
  • Cautare binara (Divide et Impera): O(log n) pe sir sortat
  • MergeSort (Divide et Impera): O(n log n), mai rapid decat sortarile simple
  • (Intensiv) Implementare C++ cu long long, tablouri si transmitere prin pointer

Vrei mai mult?

Provocare: Modifica cautare_binara ca sa gaseasca prima aparitie a unei valori intr-un sir sortat cu duplicate, de exemplu [1, 3, 3, 3, 5, 7] cautand 3 (raspuns corect: indicele 1, nu oricare din cei trei). Indiciu: cand gasesti o potrivire, nu te opri - continua cautarea in jumatatea stanga si retine cel mai mic indice gasit pana acum.

De gandit: MergeSort are nevoie de o lista auxiliara (memorie O(n)) pentru interclasare, in timp ce Selectia si Bulele (lectia 1) sorteaza direct in tabloul original, fara memorie in plus. Ce castiga MergeSort cu acest cost suplimentar de memorie, si de ce merita schimbul?

Dincolo de lectie: Cautarea binara e principiul din spatele indexilor bazelor de date (B-tree), care gasesc o inregistrare printre milioane in doar cateva zeci de pasi. Divide et Impera sta si la baza FFT (Fast Fourier Transform), algoritmul care face posibila comprimarea audio si a imaginilor in timp real.

Ai terminat modulul!

Aceasta este ultima lectie din Modulul 2. Revino la index pentru a vedea toate lectiile parcurse.

Inapoi la modul →