Programare Competitivă

Probleme simple rezolvate recursiv

Acum că știm ce e recursivitatea, aplicăm-o la câteva probleme clasice. Fiecare are o definiție recursivă naturală care se transformă imediat în cod.

1. Suma primelor n numere

Definiție recursivă

S(n) = S(n-1) + n, pentru n >= 1
S(0) = 0

Cod

int suma(int n) {
    if (n == 0) return 0;
    return suma(n - 1) + n;
}

Complexitate

  • Timp: O(n) - un apel per nivel
  • Spațiu: O(n) - stiva de apeluri

2. Factorial

Definiție recursivă

n! = n * (n-1)!, pentru n >= 1
0! = 1

Cod

long long factorial(int n) {
    if (n == 0) return 1;
    return (long long)n * factorial(n - 1);
}

Atenție: folosim long long pentru că factorialele cresc foarte repede. 13! nu mai încape în int.

Pas cu pas: factorial(4)

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

3. Ridicare la putere

Vrem a^n folosind recursivitate.

Definiție recursivă simplă

a^n = a * a^(n-1), pentru n >= 1
a^0 = 1

Cod simplu - O(n)

long long putere(int a, int n) {
    if (n == 0) return 1;
    return a * putere(a, n - 1);
}

Varianta rapidă - O(log n)

Folosim observația:

a^(2k) = (a^k)^2
a^(2k+1) = a * (a^k)^2
long long putereRapida(int a, int n) {
    if (n == 0) return 1;
    long long jum = putereRapida(a, n / 2);
    if (n % 2 == 0) return jum * jum;
    return a * jum * jum;
}

Pentru a = 2, n = 10:

putereRapida(2, 10) = putereRapida(2, 5)^2 = 32^2 = 1024
putereRapida(2, 5)  = 2 * putereRapida(2, 2)^2 = 2 * 16 = 32
putereRapida(2, 2)  = putereRapida(2, 1)^2 = 4
putereRapida(2, 1)  = 2 * putereRapida(2, 0)^2 = 2
putereRapida(2, 0)  = 1

Doar 4 apeluri în loc de 10 - log(10) ≈ 3.3.

4. Cel mai mare divizor comun (CMMDC)

Algoritmul lui Euclid recursiv

gcd(a, b) = gcd(b, a mod b), dacă b != 0
gcd(a, 0) = a

Cod

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Pentru gcd(48, 18):

gcd(48, 18) = gcd(18, 48 % 18) = gcd(18, 12)
gcd(18, 12) = gcd(12, 18 % 12) = gcd(12, 6)
gcd(12, 6)  = gcd(6, 12 % 6)   = gcd(6, 0)
gcd(6, 0)   = 6

Complexitate: O(log(min(a, b))) - foarte rapid.

5. Fibonacci - varianta naivă

F(n) = F(n-1) + F(n-2), pentru n >= 2
F(0) = 0
F(1) = 1

Cod

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Problema: exponențial!

Pentru fibonacci(5):

                fib(5)
               /      \
          fib(4)      fib(3)
         /     \      /    \
      fib(3) fib(2) fib(2) fib(1)
      /   \    ...   ...
   fib(2) fib(1)

fib(3) e calculat de 2 ori, fib(2) de 3 ori. Asta duce la complexitate O(2^n) - dezastruos pentru n > 40.

Varianta eficientă (cu accumulator)

long long fibonacci(int n, long long a = 0, long long b = 1) {
    if (n == 0) return a;
    return fibonacci(n - 1, b, a + b);
}

O(n) timp, O(n) spațiu pe stivă. Încă recursiv, dar fiecare valoare calculată o singură dată.

Lecție importantă: nu orice definiție recursivă duce la cod eficient. Fibonacci naiv e O(2^n) - folosim memoization (programare dinamică) sau iterativ pentru eficiență.

6. Suma cifrelor unui număr

Definiție recursivă

sumaCifre(n) = sumaCifre(n / 10) + (n % 10), pentru n > 0
sumaCifre(0) = 0

Cod

int sumaCifre(int n) {
    if (n == 0) return 0;
    return sumaCifre(n / 10) + n % 10;
}

Pentru n = 1234:

sumaCifre(1234) = sumaCifre(123) + 4
sumaCifre(123)  = sumaCifre(12) + 3
sumaCifre(12)   = sumaCifre(1) + 2
sumaCifre(1)    = sumaCifre(0) + 1
sumaCifre(0)    = 0
Rezultat: 0 + 1 + 2 + 3 + 4 = 10

7. Inversul unui număr

Definiție (iterativă, dar mai complicată recursiv)

Putem construi inversul cifră cu cifră. Varianta recursivă are nevoie de un parametru acumulator:

int invers(int n, int rez = 0) {
    if (n == 0) return rez;
    return invers(n / 10, rez * 10 + n % 10);
}

Pentru n = 1234:

invers(1234, 0)    → invers(123, 4)
invers(123, 4)     → invers(12, 43)
invers(12, 43)     → invers(1, 432)
invers(1, 432)     → invers(0, 4321)
invers(0, 4321)    → 4321

8. Numărul de cifre

int nrCifre(int n) {
    if (n == 0) return 0; // atentie: 0 are 0 cifre aici (ajustare daca e nevoie)
    return 1 + nrCifre(n / 10);
}

Pentru n = 12345:

nrCifre(12345) = 1 + nrCifre(1234) = 1 + 4 = 5
nrCifre(1234)  = 1 + nrCifre(123)  = 1 + 3 = 4
nrCifre(123)   = 1 + nrCifre(12)   = 1 + 2 = 3
nrCifre(12)    = 1 + nrCifre(1)    = 1 + 1 = 2
nrCifre(1)     = 1 + nrCifre(0)    = 1 + 0 = 1
nrCifre(0)     = 0

Cod complet: test toate funcțiile

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int suma(int n) { return n == 0 ? 0 : suma(n - 1) + n; }

long long factorial(int n) { return n == 0 ? 1 : (long long)n * factorial(n - 1); }

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

long long fib(int n, long long a = 0, long long b = 1) {
    return n == 0 ? a : fib(n - 1, b, a + b);
}

int sumaCifre(int n) { return n == 0 ? 0 : sumaCifre(n / 10) + n % 10; }

int main() {
    int n;
    fin >> n;

    fout << "suma 1.." << n << " = " << suma(n) << "\n";
    fout << n << "! = " << factorial(n) << "\n";
    fout << "gcd(" << n << ", 48) = " << gcd(n, 48) << "\n";
    fout << "fib(" << n << ") = " << fib(n) << "\n";
    fout << "suma cifre(" << n << ") = " << sumaCifre(n) << "\n";

    return 0;
}

date.in:

5

date.out:

suma 1..5 = 15
5! = 120
gcd(5, 48) = 1
fib(5) = 5
suma cifre(5) = 5

Cum identifici o problemă recursivă?

Pune-ți întrebarea: “Pot rezolva problema mai ușor dacă am deja răspunsul pentru o variantă mai mică?”

Exemple:

  • suma(n) - “dacă știu suma(n-1), răspunsul e suma(n-1) + n”
  • n! - “dacă știu (n-1)!, răspunsul e n * (n-1)!”
  • gcd(a, b) - “dacă b = 0, e a; altfel, gcd(b, a%b) - același tip de problemă, dar mai mic”
  • a^n - “dacă știu a^(n-1), răspunsul e a * a^(n-1)”

Dacă da, ai o soluție recursivă naturală.

Greșeli frecvente

1. Caz de bază greșit

int factorial(int n) {
    if (n == 1) return 1;       // Ce fac cu factorial(0)?
    return n * factorial(n - 1);
}

Pentru factorial(0): apelează factorial(-1), apoi factorial(-2), … → stack overflow.

Caz de bază corect: if (n <= 1) return 1; sau if (n == 0) return 1;.

2. Overflow pentru valori mari

int factorial(int n) { ... }  // int tine pana la 12!
long long factorial(int n) { ... } // long long pana la 20!

Pentru factorial mai mari, folosește aritmetică modulară sau BigInteger.

3. Apel recursiv care nu micșorează

int f(int n) {
    if (n == 0) return 0;
    return f(n); // bucla infinita!
}

Verifică: parametrul se schimbă strict în apelul recursiv.

4. Fibonacci naiv pentru n mare

fibonacci(50); // prea lent - ~10^10 apeluri

Folosește varianta cu acumulator sau iterativă pentru n mare.

Ce să reții

  • Multe probleme matematice au definiții recursive naturale.
  • Exemple clasice:
    • Suma 1..n, factorial, a^n, CMMDC, Fibonacci, suma cifrelor, invers număr
  • Fibonacci naiv e O(2^n) - foarte lent. Folosește accumulator sau memoization.
  • CMMDC recursiv (Euclid) e O(log min(a,b)) - foarte rapid.
  • Ridicarea la putere rapidă recursivă e O(log n) - folosește proprietatea a^(2k) = (a^k)^2.
  • Cheia: “dacă știu răspunsul pentru n-1 (sau n/2), cum îl obțin pe cel pentru n?”
Cuprins Inapoi Inainte