Python de la zero

2. Ce este recursivitatea?

O funcție recursivă trebuie să aibă două elemente:

Exemplu: afișarea numerelor

def afiseaza(n):
    if n == 0:
        return
    afiseaza(n - 1)
    print(n)

afișeaza(5)

3. Cum funcționează apelurile recursive?

La fiecare apel recursiv, Python trebuie să păstreze informațiile despre apelul curent. Putem urmări apelurile ca pe o stivă.

afiseaza(3)
→ afiseaza(2)
  → afiseaza(1)
    → afiseaza(0)
      → return
    → print(1)
  → print(2)
→ print(3)

4. Recursivitate cu parametri și return

În Partea 3 am învățat funcții, parametri și return. Aici le combinăm cu recursivitatea.

Factorialul

Matematic:

0! = 1
n! = n · (n-1)!

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

Pentru 5: 5 · 4 · 3 · 2 · 1 · 1 = 120.

Sumă de la 1 la n

def suma(n):
    if n == 0:
        return 0
    return n + suma(n - 1)

print(suma(5))

5. Recursivitate și liste

Putem folosi un indice pentru a spune ce element al listei prelucrăm.

Suma elementelor

def suma_lista(a, i):
    if i == len(a):
        return 0
    return a[i] + suma_lista(a, i + 1)

print(suma_lista([4, 7, 2, 9], 0))

Cea mai mare valoare

def maxim_lista(a, i):
    if i == len(a) - 1:
        return a[i]
    m = maxim_lista(a, i + 1)
    if a[i] > m:
        return a[i]
    return m

6. Ce este Backtracking?

Modelul general

def backtracking(pozitie):
    if am_completat_solutia:
        afisez_solutia()
        return

    for varianta in variante:
        if este_valida(varianta):
            aleg(varianta)
            backtracking(pozitie + 1)
            anulez(varianta)

Ultimul pas este esențial: după revenirea din apel, refacem starea pentru a putea încerca următoarea variantă.

7. Arborele soluțiilor

Backtracking-ul poate fi înțeles vizual ca o explorare a unui arbore. Fiecare nod reprezintă o alegere parțială, iar fiecare ramură reprezintă o posibilitate.

                 început
              /     |     \
             A      B      C
           / | \  / \   / | \
          ...     ...     ...

8. Permutări

O permutare este o așezare a tuturor elementelor într-o anumită ordine. Pentru [1,2,3] avem 6 permutări.

Ideea algoritmului

La poziția curentă încercăm fiecare element care nu a fost folosit.

a = [1, 2, 3]
sol = [0, 0, 0]
folosit = [False, False, False]

def permutari(k):
    if k == len(a):
        print(sol)
        return

    for i in range(len(a)):
        if not folosit[i]:
            sol[k] = a[i]
            folosit[i] = True
            permutari(k + 1)
            folosit[i] = False

permutari(0)

9. Combinări

Într-o combinație alegem mai multe elemente, dar ordinea lor nu contează. De exemplu, {1,3} și {3,1} reprezintă aceeași combinație.

Pentru a evita repetarea aceleiași combinații, următoarea alegere începe de la un indice mai mare.

a = [1, 2, 3, 4]
sol = [0, 0]

def combinari(k, start):
    if k == 2:
        print(sol)
        return

    for i in range(start, len(a)):
        sol[k] = a[i]
        combinari(k + 1, i + 1)

combinari(0, 0)

10. Aranjamente

La aranjamente alegem mai multe elemente, iar ordinea contează. Un element nu poate fi folosit de două ori în aceeași soluție.

a = [1, 2, 3, 4]
sol = [0, 0]
folosit = [False] * len(a)

def aranjamente(k):
    if k == 2:
        print(sol)
        return

    for i in range(len(a)):
        if not folosit[i]:
            sol[k] = a[i]
            folosit[i] = True
            aranjamente(k + 1)
            folosit[i] = False

aranjamente(0)

11. Backtracking pe matrice

O matrice poate reprezenta o tablă. Putem folosi backtracking pentru probleme în care trebuie să construim un drum, să plasăm obiecte sau să alegem poziții respectând reguli.

Exemplu conceptual: drum într-o matrice

La fiecare pas putem încerca direcții posibile. Dacă poziția este în afara matricei, este ocupată sau nu respectă regula problemei, alegerea este respinsă.

def drum(i, j):
    if am_ajuns_la_destinatie:
        afisez_drumul()
        return

    for directie in directii:
        ni = i + directie[0]
        nj = j + directie[1]

        if pozitia_este_valida(ni, nj):
            marchez(ni, nj)
            drum(ni, nj)
            demarchez(ni, nj)

12. Cum construim o soluție de Backtracking?

1. Identificăm ce trebuie construit.
2. Stabilim ce înseamnă o poziție din soluție.
3. Stabilim variantele posibile la fiecare poziție.
4. Scriem condiția de validitate.
5. Stabilim cazul în care soluția este completă.
6. Facem alegerea.
7. Apelăm recursiv.
8. Anulăm alegerea după revenire.

13. Exerciții rezolvate

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

n = int(input())
print(factorial(n))

def suma_cifre(n):
    if n == 0:
        return 0
    return n % 10 + suma_cifre(n // 10)

n = int(input())
print(suma_cifre(n))

def numar_cifre(n):
    if n < 10:
        return 1
    return 1 + numar_cifre(n // 10)

n = int(input())
print(numar_cifre(n))

def putere(a, n):
    if n == 0:
        return 1
    return a * putere(a, n - 1)

print(putere(2, 5))

def palindrom(s, st, dr):
    if st >= dr:
        return True
    if s[st] != s[dr]:
        return False
    return palindrom(s, st + 1, dr - 1)

s = input()
print(palindrom(s, 0, len(s) - 1))

a = [1, 2, 3]
sol = []

def submultimi(k):
    if k == len(a):
        print(sol)
        return

    submultimi(k + 1)
    sol.append(a[k])
    submultimi(k + 1)
    sol.pop()

submultimi(0)

a = [1, 2, 3]
sol = [0] * len(a)
folosit = [False] * len(a)

def permutari(k):
    if k == len(a):
        print(sol)
        return
    for i in range(len(a)):
        if not folosit[i]:
            sol[k] = a[i]
            folosit[i] = True
            permutari(k + 1)
            folosit[i] = False

permutari(0)

a = [1, 2, 3, 4]
sol = [0, 0]

def combinari(k, start):
    if k == 2:
        print(sol)
        return
    for i in range(start, len(a)):
        sol[k] = a[i]
        combinari(k + 1, i + 1)

combinari(0, 0)

sol = [0] * n

def valid(k, col):
    for i in range(k):
        if sol[i] == col:
            return False
        if abs(sol[i] - col) == abs(i - k):
            return False
    return True

def regine(k):
    if k == n:
        print(sol)
        return
    for col in range(n):
        if valid(k, col):
            sol[k] = col
            regine(k + 1)

regine(0)

sol = [0] * n

def binare(k):
    if k == n:
        print(sol)
        return
    sol[k] = 0
    binare(k + 1)
    sol[k] = 1
    binare(k + 1)

binare(0)

Exerciții propuse

14. Recapitulare și checklist